Cho một đồ thị có hướng gồm ~ n ~ đỉnh, đánh số từ ~ 1 ~ đến ~ n ~, và ~ m ~ cạnh.
Hãy thực hiện duyệt theo chiều sâu (Depth-First Search – DFS) trên đồ thị này.

Khi thực hiện DFS, ta theo dõi một biến đếm thời gian Time, ban đầu bằng 0.
Với mỗi đỉnh ~ u ~:

• Khi bắt đầu thăm ~ u ~, tăng Time lên 1 và ghi nhận giá trị này là thời gian duyệt đến của ~ u ~, ký hiệu ~ d[u] ~.
• Sau khi đã duyệt xong tất cả các đỉnh kề của ~ u ~, tăng Time lên 1 và ghi nhận giá trị này là thời gian duyệt xong của ~ u ~, ký hiệu ~ f[u] ~.

Nếu vẫn còn đỉnh nào chưa được thăm, DFS sẽ tiếp tục bắt đầu từ đỉnh nhỏ nhất chưa được thăm.

Khi duyệt từ một đỉnh ~ u ~, các đỉnh kề được xét theo đúng thứ tự xuất hiện trong dữ liệu đầu vào.

Yêu cầu

Hãy in ra thời gian duyệt đến ~ d[u] ~ và thời gian duyệt xong ~ f[u] ~ của từng đỉnh ~ u ~ từ 1 đến ~ n ~.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~ n, m ~ — số đỉnh và số cạnh của đồ thị.
• ~ m ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ u, v ~, biểu diễn một cạnh có hướng từ ~ u ~ đến ~ v ~.

Kết quả ra

• In ra ~ n ~ dòng, dòng thứ ~ i ~ chứa hai số nguyên ~ d[i] ~ và ~ f[i] ~, cách nhau bởi một dấu cách — tương ứng là thời gian duyệt đến và thời gian duyệt xong của đỉnh ~ i ~.

Giới hạn

• ~ 1 \le n \le 10^5 ~
• ~ 0 \le m \le 2\times10^5 ~
• ~ 1 \le u, v \le n ~

Ví dụ

Input

6 7
1 2
1 3
2 4
3 4
4 5
5 6
3 6

Output

1 12
2 9
10 11
3 8
4 7
5 6

Giải thích

• Bắt đầu từ đỉnh 1 → Time = 1, nên d[1] = 1.
• Từ 1 đi theo thứ tự nhập cạnh: đầu tiên là 2, rồi 3.
• Từ 2 đi đến 4, 4 đi đến 5, 5 đi đến 6.
• Mỗi khi rời khỏi một đỉnh, thời gian lại tăng thêm 1 để ghi f[u].
• Khi toàn bộ đỉnh đã được duyệt, giá trị Time cuối cùng là ~ 2n = 12 ~.

Ghi chú

• Với cùng một dữ liệu đầu vào (thứ tự các cạnh cố định), kết quả của bài toán là duy nhất.
• Nếu thay đổi thứ tự nhập các cạnh, kết quả có thể khác do thứ tự duyệt thay đổi.