Вам дан ориентированный граф. Известно, что все его вершины достижимы из вершины s=1. Найдите время входа и выхода при обходе в глубину, производя первый запуск из вершины s. Считайте, что время входа в стартовую вершину равно 0. Соседей каждой вершины обходите в порядке увеличения номеров.
В первой строке дано число вершин n (1 ≤ n ≤ 2⋅ 105) и рёбер (0 ≤ m ≤ 2 ⋅ 105). В каждой из следующих m строк записаны рёбра графа в виде пар (from, to), 1 ≤ from ≤ n — начало ребра, 1 ≤ to ≤ n — его конец. Гарантируется, что в графе нет петель и кратных рёбер.
Выведите n строк, в каждой из которых записана пара чисел tini, touti — время входа и выхода для вершины i.
|
6 8 2 6 1 6 3 1 2 5 4 3 3 2 1 2 1 4 |
0 11 1 6 8 9 7 10 2 3 4 5 |
|
3 2 1 2 2 3 |
0 5 1 4 2 3 |