graf

Time limit: 0.03s
Memory limit: 16MB
Input: graf.in
Output: graf.out

Se ştie că într-un graf neorientat conex, între oricare două vârfuri există cel puţin un lanţ iar lungimea unui lanţ este egală cu numărul muchiilor care-l compun. Definim noţiunea lanţ optim între două vârfuri XX şi YY ca fiind un lanţ de lungime minimă care are ca extremităţi vârfurile XX şi YY. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanţuri optime, depinzând de configuraţia grafului.

Cerinţă:

Fiind dat un graf neorientat conex cu NN vârfuri etichetate cu numerele de ordine 1,2,...,N1, 2, ..., N şi două vârfuri ale sale notate XX şi YY (1X,YN,XY1 ≤ X, Y ≤ N, X \neq Y), se cere să scrieţi un program care determină vârfurile care aparţin tuturor lanţurilor optime dintre XX şi YY.

Date de intrare:

Fişierul graf.in conţine

  • pe prima linie patru numere naturale reprezentând: NN (numărul de vârfuri ale grafului), MM (numărul de muchii), XX şi YY (cu semnificaţia din enunţ).
  • pe următoarele MM linii câte două numere naturale nenule Ai,BiA_i, B_i (1Ai,BiN,AiBi1 ≤ A_i, B_i ≤ N, A_i \neq B_i , pentru 1iM1 ≤ i ≤ M ) fiecare dintre aceste perechi de numere reprezentând câte o muchie din graf.

Date de ieşire:

Fişierul graf.out va conţine

  • pe prima linie, numărul de vârfuri comune tuturor lanţurilor optime dintre XX şi YY;
  • pe a doua linie, numerele corespunzătoare etichetelor acestor vârfuri, dispuse în ordine crescătoare; între două numere consecutive de pe această linie se va afla câte un spaţiu.

Restricţii:

  • 2N7 5002 ≤ N ≤ 7\ 500
  • 1M14 0001 ≤ M ≤ 14\ 000
  • pentru 5050% din teste N200N ≤ 200

Exemple

graf.in

6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4

graf.out

3
1 4 5

graf.in

3 2 1 3
1 2
3 1

graf.out

2
1 3

Problem info

ID: 49

Editor: liviu

Author:

Source: OJI 2006 XI-XII: Problema 1

Tags:

OJI 2006 XI-XII

Log in or sign up to be able to send submissions!