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

The first line contains number of vertices $n(n\le 100)$ 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.

Examples