Przeszukiwanie grafu w głąb

Limit czasu: 1s | Limit pamięci: 64MB

Napisz program, który wczyta graf skierowany $G = (V, E)$ i przeszuka go w głąb. Dla każdego wierzchołka $u$ wyznacz czas wejścia do wierzchołka $d[u]$ oraz czas zakończenia przetwarzania $f[u]$. Przyjmij, że:

• Wierzchołki identyfikowane są za pomocą identyfikatorów: $1, 2, \ldots, n$.
• Identyfikatory na listach sąsiedztwa są ułożone w kolejności rosnącej.
• Gdy do odwiedzenia jest kilku kandydatów, algorytm powinien wybrać wierzchołek o najmniejszym identyfikatorze.

Wejście

W pierwszym wierszu podana jest liczba naturalna $n$ oznaczająca liczbę wierzchołków. W kolejnych $n$ wierszach podane są listy sąsiedztwa kolejnych wierzchołków podane w następującym formacie:

$u$ $k$ $v_1$ $v_2$ ... $v_k$

$u$ to identyfikator wierzchołka, $k$ oznacza liczbę krawędzi wychodzących z tego wierzchołka, $v_i$ to identyfikatory wierzchołków sąsiadujących z $u$.

Wyjście

Dla każdego wierzchołka wypisz w linii $u$, $d$ i $f$.
$u$ to identyfikator wierzchołka, $d$ i $f$ to odpowiednio czas wejścia do wierzchołka i czas zakończenia jego przetwarzania. Kolejne linie wypisz w kolejności rosnących identyfikatorów.

Ograniczenia

• $1 \leq n \leq 100$

Przykłady

Wejście 1

4
1 1 2
2 1 4
3 0
4 1 3

Wyjście 1

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

Wejście 2

6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0

Wyjście 2

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