Under construction

Still being built. Things may change

DFS and BFS

Interview

Time limit2sMemory limit128 MB

Summary
Given an undirected graph, output the vertex visit order for DFS then BFS starting from a given vertex, always preferring the smallest-numbered neighbor.
Level

Easy3 of 10

Topics
DFS, BFS, Graph
Solved
No attempts yet

Problem

Write a program that prints the order in which the given graph is visited by depth-first search (DFS), and then by breadth-first search (BFS). When several vertices can be visited next, always visit the vertex with the smallest number first. Stop when there are no more vertices reachable from the current traversal. The vertices are numbered from 1 through N.

Input

The first line contains three integers N, M, and V: the number of vertices, the number of edges, and the starting vertex of the traversal.

  • 1 <= N <= 1,000
  • 1 <= M <= 10,000

Each of the next M lines contains two vertex numbers connected by an edge. There may be multiple edges between the same pair of vertices. All edges are undirected.

Output

Print the DFS visit order on the first line and the BFS visit order on the second line. In each line, print the vertices in the order they are visited, starting from V.

Examples3

  1. Example 1

    Input
    4 5 1
1 2
1 3
1 4
2 4
3 4
    Expected output
    1 2 4 3
1 2 3 4

  2. Example 2

    Input
    5 5 3
5 4
5 2
1 2
3 4
3 1
    Expected output
    3 1 2 5 4
3 1 4 2 5

  3. Example 3

    Input
    1000 1 1000
999 1000
    Expected output
    1000 999
1000 999