Run breadth-first search from s using outgoing edges. Enqueue smaller neighbors first.

Input

The first line contains n, m, and s. The next m lines contain directed edges.

• 1 <= s <= n <= 1000
• 0 <= m <= n(n-1)

Output

Print the visited vertices in BFS order on one line.

Example

Input

5 5 1
1 3
1 2
2 4
3 4
4 5

Output

1 2 3 4 5