Problem:
Depth First Search Depth-first search (DFS) follows the strategy to search ”deeper” in the graph whenever possible. In DFS, edges are recursively explored out of the most recently discovered vertex $v$ that still has unexplored edges leaving it. When all of $v$'s edges have been explored, the search ”backtracks” to explore edges leaving the vertex from which $v$ was discovered. This process continues until all the vertices that are reachable from the original source vertex have been discovered. If any undiscovered vertices remain, then one of them is selected as a new source and the search is repeated from that source. DFS timestamps each vertex as follows:  $d[v]$ records when $v$ is first discovered.  $f[v]$ records when the search finishes examining $v$’s adjacency list.  Write a program which reads a directed graph $G = (V, E)$ and demonstrates DFS on the graph based on the following rules:  $G$ is given in an adjacency-list. Vertices are identified by IDs $1, 2,... n$ respectively.  IDs in the adjacency list are arranged in ascending order.  The program should report the discover time and the finish time for each vertex.  When there are several candidates to visit during DFS, the algorithm should select the vertex with the smallest ID.  The timestamp starts with 1.  Input In the first line, an integer $n$ denoting the number of vertices of $G$ is given. In the next $n$ lines, adjacency lists of $u$ are given in the following format: $u$ $k$ $v_1$ $v_2$ ... $v_k$ $u$ is ID of the vertex and $k$ denotes its degree. $v_i$ are IDs of vertices adjacent to $u$. Output For each vertex, print $id$, $d$ and $f$ separated by a space character in a line. $id$ is ID of the vertex, $d$ and $f$ is the discover time and the finish time respectively. Print in order of vertex IDs. Constraints  $1 \leq n \leq 100$  Sample Input 1 4
1 1 2
2 1 4
3 0
4 1 3 Sample Output 1 1 1 8
2 2 7
3 4 5
4 3 6 Sample Input 2 6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0 Sample Output 2 1 1 12
2 2 11
3 3 8
4 9 10
5 4 7
6 5 6   This is example for Sample Input 2 (discover/finish)  Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
from collections import deque
n = int(input())
data = [None]*n
unvisited = [1]*n
for _ in range(n):
    a,*b = map(int,input().split())
    a -= 1
    data[a] = deque([i-1 for i in b[1:]])

d = [-1]*n
f = [-1]*n
t = 0

dq = deque([])
for u in range(n):
    if unvisited[u]:
        dq.append(u)
        unvisited[u] = 0
        t += 1
        d[u] = t
        while dq:
            k = dq[-1]
            if data[k]:
                v = data[k].popleft()
                if unvisited[v]:
                    unvisited[v] = 0
                    t += 1
                    d[v] = t
                    dq.append(v)
            else:
                dq.pop()
                t += 1
                f[k] = t

for i in range(n):
    print(i+1,d[i],f[i])

Solution (Python):




import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self,x,y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self,i,adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def path_detector(self, start=0, time=0):
        """
        :param p: スタート地点
        :return: 各点までの距離と何番目に発見したかを返す
        """

        edge2= []
        for i in range(self.n):
            edge2.append(sorted(self.edge[i], reverse=True))

        p, t = start, time
        self.parent[p] = -2
        full_path = [(p + self.decrement,t)]
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                self.parent[q] = p
                p, t = q, t + 1
                full_path.append((p + self.decrement, t))
            else:
                """ 探索完了時の処理 """
                full_path.append((p + self.decrement, t))
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """
                """"""""""""""""""""
        return full_path

    def path_list(self):
        """
        :return: 探索経路を返す。
        """
        self.parent = [-1]*self.n
        res = []
        for p in range(self.n):
            if self.parent[p] == -1:
                res.append(self.path_detector(start=p, time=1))
        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.dictated:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y in self.edge[x]:
                G.add_edge(x + self.decrement, y + self.decrement)
        nx.draw_networkx(G)
        plt.show()

def make_graph(dictated=False, decrement=True):
    """
    自己ループの無いグラフを生成。N>=2
    :param dictated: True = 有効グラフ
    :param decrement: True = 1-indexed
    :return:
    """
    import random
    N = random.randint(2, 5)
    if N > 2:
        M_max = (3*N-6)*(1+dictated)
    else:
        M_max = 1
    graph = Graph(N, dictated, decrement)
    for _ in range(random.randint(0,M_max)):
        graph.add_edge(*random.sample(range(decrement, N+decrement), 2))
    return graph





N = int(input())  

graph = Graph(N,dictated=True, decrement=True)

for i in range(N):  
    points = list(map(int, input().split()))[2:]
    graph.add_adjacent_list(i, points)


data = graph.path_list()

from itertools import chain
data = list(chain.from_iterable(data))

res = [[i+1,0,0] for i in range(N)]
for time, a in enumerate(data, start=1):
    i = a[0] - 1
    if res[i][1]:
        res[i][2] = time
    else:
        res[i][1] = time

for a in res:
    print(*a)

Solution (Python):
n = int(input()) 
path = list() 
path.append([])
for _ in range(n):
    tmp = list(map(int, input().split())) 
    path.append(tmp[2:])

d = [0]*(n+1) 
f = [0]*(n+1) 

TIME = 0

def dfs(p, d, f):
    global TIME
    TIME += 1
    d[p] = TIME 

    for nxt in path[p]: 
        if d[nxt] == 0: 
            dfs(nxt, d, f) 
    
    TIME += 1
    f[p] = TIME 

    
    return     
    
for start in range(1, n+1):
    if d[start] == 0:
        dfs(start, d, f)

for i in range(1, n+1):
    print(i, d[i], f[i])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
idx = 1


def resolve():
    def dfs(v):
        global idx
        begin[v] = idx
        idx += 1
        for u in edge[v]:
            if begin[u] != 0:
                continue
            else:
                dfs(u)
        end[v] = idx
        idx += 1

    n = int(input())
    edge = [[] for _ in range(n)]
    for _ in range(n):
        u, k, *V = map(int, input().split())
        for v in V:
            edge[u - 1].append(v - 1)

    begin = [0] * n
    end = [0] * n
    for i in range(n):
        if begin[i] == 0:
            dfs(i)
    for i in range(n):
        print(i + 1, begin[i], end[i])


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import defaultdict


def dfs(v, t):
    if start[v] == 0:
        start[v] = t
        t += 1
    else:
        return t

    for nv in graph[v]:
        t = dfs(nv, t)

    end[v] = t
    t += 1

    return t


n = int(input())

graph = defaultdict(list)

for _ in range(n):
    u, k, *v = map(int, input().split())
    for v in v:
        graph[u].append(v)

start = [0] * (n + 1)
end = [0] * (n + 1)


t = 1

for i in range(1, n + 1):
    t = dfs(i, t)

for i in range(1, n + 1):
    print(i, start[i], end[i])

Solution (Python):
N = int(input())
adj_list = [ [] for _ in range(N+1) ]
for _ in range(N):
  lst = list(map(int,input().split()))
  node = lst[0]
  if lst[1] != 0:
    adj_list[node] = lst[2:]


visited = [False] * (N+1)
arrived = [-1] * (N+1)
left = [-1] * (N+1)

time = 0
def dfs(node):
  global time

  arrived[node] = time
  visited[node] = True

  for nei in adj_list[node]:
    if not visited[nei]:
      time += 1
      dfs(nei)
  else:
    time += 1
    left[node] = time

for i in range(1, N+1):
  if not visited[i]:
    time += 1
    dfs(i)

for i in range(1, N+1):
  print(i, arrived[i], left[i])

Solution (Python):
n = int(input())
link = {}

for i in range(n):
    a = list(map(int, input().split()))
    a.reverse()

    u, k = a.pop(), a.pop()
    link[u] = []
    for j in range(k):
        link[u] += [a.pop()]

d, f = {}, {}
t = 0


def dfs(u):
    global t
    t += 1
    d[u] = t

    for v in link[u]:
        if v not in d: dfs(v)

    if u not in f:
        t += 1
        f[u] = t


for u in range(1, n + 1):
    if u not in d: dfs(u)

for i in range(1, n + 1):
    print(i, d[i], f[i])

Solution (Python):
def main():
    n=int(input())
    u,k,v=0,0,[[] for _ in range(n+1)]
    for i in range(n):
        l=list(map(int,input().split()))
        u=l[0]
        for j in l[2:]:
            v[u].append(j)
    d=[0]*(n+1)
    f=[0]*(n+1)

    def dfs(s,t):
        d[s]=t
        for i in v[s]:
            if d[i]==0:
                t=dfs(i,t+1)
        f[s]=t+1
        return t+1

    s,t=1,1
    while 0 in d[1:]:
        T=dfs(s,t)
        for i in range(1,n+1):
            if d[i]==0:
                s=i
                t=T+1
                break

    for i in range(1,n+1):
        print(i,d[i],f[i])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n = int(input())
u = []
k = []
v = []

for i in range(n):
    tmp = list(map(int, input().split()))
    u.append(tmp[0])
    k.append(tmp[1])
    if tmp[1] != 0:
        v.append(tmp[2:])
    else:
        v.append([])
        
check = [0]*n
intime = [0]*n
outtime = [0]*n
time = 1

def dfs(v, start):
    d = deque()
    d.append(start)
    global check
    global intime
    global outtime
    global time
    check[start-1] = 1
    intime[start-1] = time
    time += 1
    while len(d) > 0:
        visit = d[-1]
        tf = True
        for dtn in v[visit-1]:
            if check[dtn-1] == 0:
                d.append(dtn)
                check[dtn-1] = 1
                intime[dtn-1] = time
                time += 1
                tf = False
                break
        if tf:
            outtime[visit-1] = time
            d.pop()
            time += 1

dfs(v, 1)
for i in range(n):
    if check[i] == 0:
        dfs(v, i+1)
for i in range(n):
    print(i+1, intime[i], outtime[i])

Solution (Python):
n = int(input())
d = [0]*n
f = [0]*n
G = [[] for _ in range(n)]
for _ in range(n):
    l = list(map(int, input().split()))
    u, k = l[:2]
    l = list(map(lambda x: x-1, l[2:]))
    G[u-1] = l

timestamp = [i+1 for i in range(2*n)]
def dfs(node):
    global d,f,G,timestamp
    if d[node]>0:
        return False
    d[node] = timestamp.pop(0)
    for v in G[node]:
        dfs(v)
    if f[node]==0:
        f[node] = timestamp.pop(0)
    return True
for i in range(n):
    dfs(i)
    
for i in range(n):
    print(i+1, d[i], f[i])

Solution (Python):
n=int(input())
g=[]
for i in range(n):
    u,k,*varray= map(int,input().split())
    g.append(varray)

time = 1
d= [-1]* n
f= [-1]* n

def dfs(src):
    global time
    d[src]= time
    time+=1
    for i in g[src]:
        if d[i-1]== -1:
            dfs(i-1)
    f[src]= time
    time+=1

for i in range(n):
    if d[i]== -1:
        dfs(i)
for i in range(n):
    print(i+1,d[i],f[i])

Solution (Python):
n=int(input())
D=[0]*(n+1)
F=[0]*(n+1)
v=[[] for i in range(n+1)]
flg=True
t=1
for i in range(n):
  a=list(map(int,input().split()))
  v[a[0]]=sorted(a[2:])

def dfs(p):
  global t
  if D[p]!=0: return
  D[p]=t
  t+=1
  for i in v[p]:
    if D[i]==0: dfs(i)
  F[p]=t
  t+=1

while flg:
  flg=False
  for i in range(1,n+1):
    if D[i]==0:
      flg=True
      dfs(i)

for i in range(1,n+1):
  print(f'{i} {D[i]} {F[i]}')

Solution (Python):
N = int(input())
M = []
for i in range(N):
    a = list(map(int,input().strip().split()))
    b = [int(i+1 in a[2:]) for i in range(N)]
    M.append(b)

time = 1
D = [-1 for _ in range(N)]
F = [-1 for _ in range(N)]
def dfs(src):
    global time 
    D[src] = time 
    time += 1
    for dst in range(N):
        
        if M[src][dst] == 1 and D[dst] == -1:
            dfs(dst)
    F[src] = time 
    time += 1
    

for root in range(N):
    
    if D[root] == -1:
        
        dfs(root) 

[print(i+1, D[i], F[i]) for i in range(N)]

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

G = [[] for _ in range(105)]
begin = [-1] * 105
end = [-1] * 105

t = 1
def dfs(v):
    global t
    begin[v] = t
    t += 1
    for e in G[v]:
        if begin[e] < 0:
            dfs(e)
    end[v] = t
    t += 1

def main():
    N = int(input())
    for i in range(N):
        A = list(map(int,input().split()))
        for a in A[2:]:
            G[i].append(a - 1)
    
    for i in range(N):
        if begin[i] < 0:
            dfs(i)
    for i in range(N):
        print(i + 1,begin[i],end[i])
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

adj = [[] for _ in range(N)]

for i in range(N):
    line = list(map(int, input().split()))
    u = line[0] - 1
    if line[1] == 0:
        continue
    vs = line[2:]
    for v in vs:
        adj[u].append(v - 1)

d = [-1] * N
f = [-1] * N

def dfs(v, t):
    d[v] = t
    nx = t + 1
    for u in adj[v]:
        if d[u] > -1:
            continue
        nx = dfs(u, nx)
    f[v] = nx
    return f[v] + 1

nx = 1
for i in range(N):
    if d[i] > - 1:
        continue
    nx = dfs(i, nx)

for i in range(N):
    print(i + 1, d[i], f[i])

Solution (Python):
N = int(input())
UKV = [list(map(int,input().split())) for _ in range(N)]

seen = [False]*N
first_time = [-1]*N
last_time = [-1]*N
time = 0
def dfs(G, v):
    global seen
    global first_time
    global last_time
    global time
    seen[v-1] = True
    time += 1
    first_time[v-1] = time
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)
    time += 1
    last_time[v-1] = time

G = {}
for ukv in UKV:
    G[ukv[0]] = sorted(ukv[2:])
for i in range(1,N+1):
    if seen[i-1]:
        continue
    dfs(G, i)

for i in range(1,N+1):
    print(i,first_time[i-1],last_time[i-1])

Solution (Python):
def dfs(v, cnt):
    D[v] = cnt
    cnt += 1
    for c in edge[v]:
        if D[c] == -1:
            cnt = dfs(c, cnt)
    F[v] = cnt
    cnt += 1
    return cnt

V = int(input())
edge = [[] for _ in range(V)]
for _ in range(V):
    u, _, *v = map(lambda x: int(x)-1, input().split())
    edge[u] = sorted(v)
D, F = [-1] * V, [-1] * V
c = 1
for i in range(V):
    if D[i] == -1:
        c = dfs(i, c)
for i, (d, f) in enumerate(zip(D, F)):
    print(i+1, d, f)

Solution (Python):
n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]

stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)
for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time

        while stack:
            s = stack[-1]
            k = ukv[s][1]
            if k == 0:
                stack.pop()
                time += 1
                f[s] = time
            else:
                ukv[s][1] -= 1
                v = ukv[s].pop(2)
                if v not in visited:
                    stack.append(v)
                    visited.append(v)
                    time += 1
                    d[v] = time

for i in range(1, n + 1):
    print(i, d[i], f[i])

Solution (Python):
n=int(input())
G=[]
for i in range(n):
    L=list(map(int,input().split()))
    G.append(L[2:])
    for j in range(len(G[-1])):
        G[-1][j]-=1

Forder=[-1]*n
Lorder=[-1]*n
ptr=1
def dfs(v):
    
    
    
    global ptr

    Forder[v]=ptr
    ptr+=1

    for next in G[v]:
        if Forder[next]!=-1:
            continue
        dfs(next)
    
    Lorder[v]=ptr
    ptr+=1




















for i in range(n):
    if Forder[i]==-1 or Lorder[i]==-1:
        dfs(i)

for i in range(n):
    print(i+1,Forder[i],Lorder[i])

Solution (Python):
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for _ in range(n):
        l=list(map(int,input().split()))
        nList[l[0]]=l[2:]
    return n,nList

WHITE=0
GRAY=1
BLACK=2
color=[]
d=[]
f=[]
_time=0

def dfs(u,nList):
    global color
    global d
    global f
    global _time

    S=[]

    if(color[u]==WHITE):
        S.append(u)
        color[u]=GRAY
        _time+=1
        d[u]=_time

    while(len(S)>0):
        u=S[-1]
        t=next(u,nList)
        if(t!=-1):
            if(color[t]==WHITE):
                S.append(t)
                color[t]=GRAY
                _time+=1
                d[t]=_time
        else:
            S.pop()
            color[u]=BLACK
            _time+=1
            f[u]=_time

def next(u,nList):
    global color
    for t in nList[u]:
        if color[t]==WHITE:
            return t
    else:
        return -1

def main(n,nList):
    global color
    global d
    global f

    color=[WHITE]*(n+1)
    d=[0]*(n+1)
    f=[0]*(n+1)

    for i in range(1,n+1):
        dfs(i,nList)
    for i in range(1,n+1):
        print('{} {} {}'.format(i,d[i],f[i]))

if __name__=='__main__':
    n,nList=readinput()
    main(n,nList)

Solution (Python):



from collections import deque

n = int(input())
u_l = []
k_l = []
v_l = []
for i in range(n):
    _in = input()
    _v_l = []
    for j,_ in enumerate(_in.split()):
        if j == 0:
            u_l.append(int(_))
        elif j == 1:
            k_l.append(int(_))
        else:
            _v_l.append(int(_))
    v_l.append(_v_l)

def dfs(v):
    global count
    c_l[v] = True
    d_l[v] = count
    count += 1
    for i in range(k_l[v]):
        _v = v_l[v][i]-1
        if not c_l[_v]:
            dfs(_v)
    f_l[v] = count
    count += 1

d_l = [None]*n
f_l = [None]*n
c_l = [False]*n
count = 1
while False in c_l:
    dfs(c_l.index(False))

for idx, d, f in zip(list(range(1,n+1)), d_l, f_l):
    print(idx, d, f)

Solution (Python):
def solve(v, g, ans, time):
    if ans[v]["found"] != 10**9:
        return time
    time += 1
    
    ans[v]["found"] = time
    for a in g[v]:
        time = solve(a, g, ans, time)
    time += 1
    
    ans[v]["complete"] = time
    return time


def resolve():
    n = int(input())
    V = [list(map(int, input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for v, k, *a in V:
        v -= 1
        for ai in a:
            ai -= 1
            g[v].append(ai)
    ans = [{"found": 10**9, "complete": -1} for _ in range(n)]
    time = solve(0, g, ans, 0)
    for i in range(n):
        if ans[i]["found"] == 10**9:
            solve(i, g, ans, time)
        print(i + 1, ans[i]["found"], ans[i]["complete"])


resolve()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(u, cnt):
    visited.add(u)
    first_contact = cnt
    
    cnt += 1
    for nb in edge[u]:
        if nb not in visited:
            cnt = DFS(nb, cnt)
    
    stamp[u] = first_contact, cnt
    return cnt+1
    

N = int(input())
edge = [[] for i in range(N)]
for _ in range(N):
    tmp = list(map(int,input().split()))
    if tmp[1] != 0:
        edge[tmp[0]-1] = list(map(lambda x: int(x-1),tmp[2:]))

stamp = [None]*N
visited = set()

c = 1
for i in range(N):
    if i not in visited:
        c = DFS(i, c)
        
for i,s in enumerate(stamp):
    print(i+1,*s)

Solution (Python):
def dfs(adjlist,v):
    global d,f,t
    d[v-1]=t
    t+=1
    for node in adjlist[v-1]:
        if d[node-1]<0 and node>0:
            dfs(adjlist,node)
    f[v-1]=t
    t+=1

n=int(input())
adjlist=[list(map(int,input().split()))[2:] for _ in range(n)]
d=[-1]*n
f=[-1]*n
t=1
for i in range(1,n):
    if d[i-1]<0:
       dfs(adjlist,i)
for i in range(n):
    print("{} {} {}".format(i+1,d[i],f[i]))

Solution (Python):
n = int(input())
G = [[] for i in range(n+1)] 
for i in range(n):
    a = [int(i) for i in input().split()]
    G[a[0]] = a[2:]
    G[a[0]].sort()

d = [0] * (n+1)
f = [0] * (n+1)

seen = [0] * (n+1) 
t = 0

def dfs(s):
    global t
    seen[s] = 1
    d[s] = t
    for i in G[s]:
        if seen[i] == 0:
            t += 1
            dfs(i)
    t += 1
    f[s] = t

for i in range(1, n+1):
    if not seen[i]:
        t += 1
        dfs(i)

for i in range(1, n+1):
    print(i, d[i], f[i])

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(10 ** 9)

n = int(input())

graph = []

for _ in range(n):
    tmp = list(map(int, input().split()))

    if tmp[1] == 0:
        graph.append([])
        continue
    else:
        graph.append(list(map(lambda x: x - 1, tmp[2: tmp[1] + 2])))

d = [-1] * n
f = [-1] * n

time = 1


def dfs(x):
    if d[x] != -1:
        return

    global time

    d[x] = time
    time += 1

    for n in graph[x]:
        dfs(n)

    f[x] = time
    time += 1


for i in range(n):
    dfs(i)

for i in range(n):
    print(i + 1, d[i], f[i])

Solution (Python):
def main():
    import sys
    N = int(sys.stdin.readline())
    L1 = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    
    edge = [[] for _ in range(N+1)]
    for row in L1:
        for ele in row[2:]:
            edge[row[0]].append(ele)
            

    
    sys.setrecursionlimit(1000)
    
    go = [-1 for _ in range(N+1)]
    go[0], go[1] =0, 1
    back = [-1 for _ in range(N+1)]
    
    d = [1]
    def dfs(p):
        if edge[p]:
            for c in edge[p]:
                if go[c]==-1:
                    d[0]+=1
                    go[c] = d[0]
                    dfs(c)
        
        
        d[0]+=1
        back[p] =d[0]
                
    dfs(1)
    for i in range(2, N+1):
        if go[i] ==-1:
            d[0]+=1
            go[i] = d[0]
            dfs(i)
    for i in range(1, N+1):
        print(i, go[i], back[i])




if __name__=='__main__':
    main()

Solution (Python):
t = 1
v, d, f = {}, {}, {}

def dfs(i):
  global t, v, d, f
  if i in d:
    return
  if i != 0:
    d[i] = t
    t += 1
  for j in v[i]:
    dfs(j)
  if i != 0:
    f[i] = t
    t += 1

n = int(input())
v[0] = list(range(1, n+1))
for i in range(n):
  tmp = list(map(int, input().split()))
  v[tmp[0]] = tmp[2:]
  v[tmp[0]].sort()
dfs(0)
for i in range(n):
  print("{} {} {}".format(i+1, d[i+1], f[i+1]))

Solution (Python):
def dfs(v):  
    global time
    seen[v] = 1
    start[v] = time
    time += 1

    for next_v in graph[v]:
        if seen[next_v]: continue
        dfs(next_v)
    
    end[v] = time
    time += 1


n = int(input())
graph = []
for _ in range(n):
    line = list(map(int, input().split()))
    graph.append([v - 1 for v in line[2:]])

seen = [0] * n  
start = [0] * n
end = [0] * n
time = 1

for v in range(n):
    if not seen[v]: dfs(v)

for i in range(n):
    print(i+1, start[i], end[i])

Solution (Python):
import sys

n = int(input())
G = [None]*(n+1)
for i in range(n):
    u, k, *vs = map(int, input().split())
    G[u] = vs

d = [-1]*(n+1)
f = [-1]*(n+1)
lb = iter(range(1, 2*n+1)).__next__
def dfs(v):
    d[v] = lb()
    for w in G[v]:
        if d[w] != -1: 
            continue
        dfs(w)
    f[v] = lb()

for v in range(1, n+1):
    if d[v] != -1:
        continue
    dfs(v)

for v in range(1, n+1):
    print(f"{v} {d[v]} {f[v]}")

Solution (Python):
from collections import deque
N=int(input())
color=["w"]*(N+1)
start=[None]*(N+1)
finish=[0]*(N+1)
rinsetu=[[] for i in range(N+1)]
for i in range(1,N+1):
    a=list(map(int,input().split()))
    a=a[2:]
    rinsetu[i]=a
def dfs(i,t):
    if color[i]=="w":
        t+=1
        start[i]=t
        color[i]="g"
        for j in rinsetu[i]:
            t=dfs(j,t)
        t+=1
        finish[i]=t
        return t
    else:return t
t=dfs(1,0)
while(None in start[1:]):
    a=start[1:].index(None)
    t=dfs(a+1,t)

for i in range(1,N+1):
    print("%d %d %d" %(i,start[i],finish[i]))

Solution (Python):
n = int(input())
G = [[] for _ in range(n)]
for _ in range(n):
    u, k, *v = map(int, input().split())
    u -= 1
    G[u].extend(v)
seen = [False] * n
d = [-1] * n
f = [-1] * n
t = 1

def dfs(v):
    global t

    d[v] = t
    t += 1
    seen[v] = True
    for next_v in G[v]:
        next_v -= 1
        if not seen[next_v]:
            t = dfs(next_v)
    f[v] = t
    t += 1
    return t

def main():


    for i in range(n):
        if not seen[i]:
            dfs(i)
    for i in range(n):
        print(i+1, d[i], f[i])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(3000)

n = int(input())
X = []
for _ in range(n):
    x = list(map(int, input().split()))
    if x[1] != 0:
        X.append(x[2:])
    else:
        X.append([])

df = [[0, 0] for _ in range(n)]
t = 0
def search(i = 0):
    global t
    if df[i][0] == 0:
        t += 1
        df[i][0] = t
    for x in X[i]:
        if df[x - 1][0] == 0:
            search(x - 1)
    if df[i][1] == 0:
        t += 1
        df[i][1] = t

for i in range(n):
    search(i)

for i, x in enumerate(df):
    print('{} {} {}'.format(i + 1, x[0], x[1]))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
from collections import deque

n = int(input())
u = [[] for i in range(n+1)] 
for i in range(n):
    v = list(map(int, input().split()))
    u[v[0]] = v[1:] 

d = [-1] * (n+1)
f = [-1] * (n+1)
visited = [False] * (n+1)
visited[0] = True
time = 1


def dfs(c):
    global time
    d[c] = time
    time += 1
    visited[c] = True
    for i in range(1, u[c][0]+1):
        if not visited[u[c][i]]:
            dfs(u[c][i])
    f[c] = time
    time += 1
"""
探索は元の始点から到達可能なすべての頂点を発見するまで続き、
未発見の頂点が残っていれば、
その中の番号が一番小さい１つを新たな始点として探索を続けます。
"""
while False in visited:
    dfs(visited.index(False))

for i in range(1, n+1):
    print(i, d[i], f[i])

Solution (Python):
def dfs(v, time_, d, f, dp):
    if d[v] == 0:
        d[v] = time_
    for i in range(len(dp[v])):
        if d[dp[v][i]] == 0:
            time_ = dfs(dp[v][i], time_ + 1, d, f, dp)
    f[v] = time_ + 1
    return time_ +  1


def main():
    N = int(input())
    dp = [[] for i in range(N)]
    for i in range(N):
        line = [int(k) for k in input().split()]
        for j in range(len(line)):
            if j == 0 or j == 1:
                continue
            dp[line[0] - 1].append(line[j] - 1)

    d = [0] * N
    f = [0] * N
    time_ = 1
    for i in range(N):
        if d[i] == 0:
            time_ = dfs(i, time_, d, f, dp)
            time_ += 1
    for i in range(N):
        print(i + 1, d[i], f[i])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
time = 1
def dfs(node):
    global time
    if visited[node] != -1:
        return
    visited[node] = 0
    d[node] = time
    time += 1
    for v in edge[node]:
        dfs(v)
    f[node] = time
    time += 1

if __name__ == "__main__":
    n = int(input())
    edge = []
    for i in range(n):
        u,k,*v_li = map(int,input().split())
        for j in range(len(v_li)):
            v_li[j] -= 1
        u-=1
        edge.append(v_li)
    d = {}
    f = {}
    visited = [-1]*n
    
    for i in range(n):
        dfs(i)
    for i in range(n):
        print(i+1,d[i],f[i])

Solution (Python):

import sys

n = int(input())
e = [None] * n
for _ in range(n):
    u, k, *v = map(int, sys.stdin.readline().strip().split())
    e[u - 1] = [i - 1 for i in v]


S = []  
time = 0
t_in = [0] * n
t_out = [0] * n
fp = [False] * n  


def dfs(u):
    global time

    S.append(u)
    time += 1
    t_in[u] = time
    fp[u] = True

    while S:
        u = S[-1]

        v = None
        for i in e[u]:
            if fp[i] is False:
                v = i
                break

        time += 1
        if v is not None:
            S.append(v)
            t_in[v] = time
            fp[v] = True

        else:
            v = S.pop()
            t_out[v] = time


while False in fp:
    dfs(fp.index(False))

for i in range(n):
    print(f'{i + 1} {t_in[i]} {t_out[i]}')

Solution (Python):
N = int(input())

nodes = [tuple(map(int, input().split(' '))) for _ in range(N)]
d = [-1 for _ in range(N + 1)]
f = [-1 for _ in range(N + 1)]

clock = 0


def dfs(node):
    global clock
    if d[node] == -1:
        clock += 1
        d[node] = clock
    neighbors = sorted(nodes[node - 1][2:])

    for neighbor in neighbors:
        if d[neighbor] == -1:
            dfs(neighbor)

    if f[node] == -1:
        clock += 1
        f[node] = clock


for i in range(1, N + 1):
    dfs(i)
    print(i, d[i], f[i])

Solution (Python):
def dfs(i):
    global t
    t += 1
    D[i] = t
    for e in es[i]:
        if D[e] == 0:
            dfs(e)
    t += 1
    F[i] = t


if __name__ == "__main__":
    N = int(input())
    es = [[] for _ in range(N+1)]
    for _ in range(N):
        ipts = [int(ipt) for ipt in input().split()]
        if ipts[1] > 0:
            es[ipts[0]] = ipts[2:]
    D = [0 for _ in range(N+1)]
    F = [0 for _ in range(N+1)]
    t = 0
    for i in range(1, N+1):
        if D[i] == 0:
            dfs(i)
    for i in range(1, N+1):
        print(i, D[i], F[i])

Solution (Python):
class Node:
    def __init__(self, data):
        self.data = data
        self.neighbors = list()
        self.find_time = 0
        self.end_time = 0

N = int(input())
work_id = 0
nodes = list()
nodes.append(Node(0))


for _ in range(N):
    tmp_list = list( map(int, input().split()) )
    node = Node(tmp_list[0])
    for i in range(tmp_list[1]):
        node.neighbors.append(tmp_list[i+2])
    nodes.append(node)
    nodes[0].neighbors.append(node.data)





def search(node):
    global work_id

    if node.find_time != 0:
        return
    
    if node.data != 0:
        work_id += 1
        node.find_time = work_id

    if len(node.neighbors) > 0:
        for neighbor in node.neighbors:
            search(nodes[neighbor])
    
    if node.data != 0:
        work_id += 1
        node.end_time = work_id

search(nodes[0])

for node in nodes:
    if node.data == 0: continue
    print(node.data, node.find_time, node.end_time)