e-olymp
Competitions

ADA Classes - Depth First Search

Depth First Search - Timestamps

Undirected graph is given. Run depth first search from the given vertex v. Print the timestamps d[v] and f[v] for each vertex v in the increasing order of vertices.

Input

First line contains number of vertices n (n100) and edges m of undirected graph. Each of the next m lines contains two vertices a and b - an undirected edge of the graph. The last line contains vertex v.

Output

Run dfs(v). Print the timestamps d[v] and f[v] for each vertex v (v = 1, 2, ..., n). The timestamps for each vertex must be printed in a separate line.

prb8761.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 3
1 2
2 3
1 3
2
Output example #1
2 5
1 6
3 4
Input example #2
5 5
1 2
2 3
2 5
2 4
1 4
3
Output example #2
3 6
2 9
1 10
4 5
7 8