An undirected graph is given. Run a depth-first search from the given vertex v. Print the timestamps d[v] and up[v] for each vertex v in the increasing order of vertices.

Input

The first line contains the number of vertices n (n ≤ 100) and edges m of an 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 up[v] for each vertex v (v = 1, 2, ..., n). The timestamps for each vertex must be printed on a separate line.

Hint

Use the adjacency matrix to get accepted.