그래프 탐색 알고리즘인 깊이 우선 탐색(DFS)을 수행하면서, 각 노드에 처음 방문한 시각인 방문 시간(Discovery Time)과 해당 노드 및 하위 탐색을 모두 마치고 돌아오는 시각인 완료 시간(Finish Time)을 기록하려고 한다.

시각은 \(1\)부터 시작하며, 새로운 노드를 방문하거나 노드의 탐색을 완료할 때마다 시각이 \(1\)씩 증가한다.

\(N\)개의 노드와 \(M\)개의 양방향 간선으로 이루어진 무방향 그래프가 주어졌을 때, \(1\)번 노드에서 출발하여 DFS를 수행하고 각 노드의 방문 시간과 완료 시간을 구하는 프로그램을 작성하시오.

< 처리조건 >

1. 시각 변수는 \(1\)부터 시작한다.
2. \(1\)번 노드를 방문하면서 시각 \(1\)이 기록된다.
3. 방문할 수 있는 인접 노드가 여러 개 있는 경우, 노드 번호가 작은 것부터 우선 방문한다.
4. \(1\)번 노드에서 출발하여 도달할 수 없는 노드의 경우, 방문 시간과 완료 시간을 모두 \(0\)으로 출력한다.

입력

첫째 줄에 노드의 개수 \(N\)과 간선의 개수 \(M\)이 공백을 사이에 두고 주어진다. (\(1 \le N \le 1,000\), \(1 \le M \le 10,000\))

둘째 줄부터 \(M\)개의 줄에 걸쳐 간선이 연결하는 두 노드 번호 \(u, v\)가 공백으로 구분되어 주어진다. (\(1 \le u, v \le N\), \(u \ne v\))

중복 간선은 주어지지 않는다.

출력

\(1\)번 노드부터 \(N\)번 노드까지 차례대로, 각 줄에 해당 노드의 방문 시간과 완료 시간을 공백으로 구분하여 출력한다.

예제 입력 1

4 3
1 2
2 3
1 4

예제 출력 1

1 8
2 5
3 4
6 7

예제 입력 2

5 3
1 2
1 3
4 5

예제 출력 2

1 6
2 3
4 5
0 0
0 0