## Problem A. Breadth First Search ≡

• problems
• en ru
 Author: StdAlg Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

You are to write a program that receives an unweighted undirected graph and writes all its vertices in order of increasing distance from given vertex S. Distance between vertices A and B is the length of the shortest path from A to B. If there are several vertices such that their distances to S are equal, they may be printed in arbitrary order.

### Input file format

Input file contains three integers N, M and S, where M is the number of edges, S is the starting vertex. Vertices are numbered with integer numbers from 1 to N. Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.

### Output file format

Output file must contain sequence of vertex numbers sorted by increasing distance from S. If some vertex is not reachable from S, output a single number  − 1.

### Constraints

0 ≤ N, M ≤ 100000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2 1
1 2
2 3
1 2 3

0.059s 0.009s 13