Depth First Search - Timestamps

Input

The first line contains the number of vertices n~(n \le 100) and the number of edges $m$ of the undirected graph. Each of the next $m$ lines contains two vertices $a$ and $b$, denoting an undirected edge of the graph. The last line contains the starting 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, in the order of increasing vertex number.

Examples