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):
import sys

global stamp, counter
stamp = {}
counter = 0

def dfs(key, GRAPH):
    global stamp, counter
    if stamp[key][0] == 0:
        counter += 1
        stamp[key][0] = counter
    elif stamp[key][1] != 0:
        return

    for e in GRAPH[key]:
        try:
            if stamp[e][0] == 0:
                dfs(e, GRAPH)
        except:
            pass
    counter += 1
    stamp[key][1] = counter
    return

n = int(raw_input())
x = {}
for i in range(n):
    seq = map(int, raw_input().split())
    key = seq[0]
    if key != 0:
        x[key] = seq[2:]
    else:
        x[key] = []  
    stamp[key] = [0, 0]

for e in x.keys():
    dfs(e, x)

for e in x.keys():
    print e, stamp[e][0], stamp[e][1]

Solution (Python):
n = int(input())
g = [None] * n
visited = [0] * n
root = set(range(n))
ts = [[0, 0] for _ in range(n)]
t = 0

while n:
    l = list(map(int, input().split()))
    connected = [i - 1 for i in l[2:]]
    g[l[0] - 1] = [i - 1 for i in l[2:]]
    root -= set(connected)
    n -= 1


def dfs(i):
    global g, t, ts, visited
    lts = ts[i]
    t += 1
    lts[0] = t
    visited[i] = 1
    for c in g[i]:
        if not visited[c]:
            dfs(c)
    t += 1
    lts[1] = t

if root:
    for r in sorted(root):
        dfs(r)
else:
    dfs(0)

for i, v in enumerate(ts):
    print(i + 1, *v)

Solution (Python):
import sys

def DFS(index, tm, l, a, b):
 tm += 1
 a[index] = tm
 for i in l[index]:
  if not a[i-1]:
   tm = DFS(i-1, tm, l, a, b)
 tm += 1
 b[index] = tm
 return tm


n = input()
l=[]
for i in xrange(n):
 l.append([int(s) for s in sys.stdin.readline().split()[2:]])
a = [0] * n
b = [0] * n
tm = 0
for i in xrange(n):
 if not a[i]:
    tm = DFS(i, tm, l, a, b)

for i in xrange(n):
   print i+1, a[i], b[i]

Solution (Python):
n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
t = [0]
 
def DFS_visit(s):
    st[s] = 1
    t[0] += 1
    d[s] = t[0]
    for e in range(n):
        if M[s][e] == 1 and st[e] == 0:
            DFS_visit(e)
    st[s] == 2
    t[0] += 1
    f[s] = t[0]
 
def DFS():
    for s in range(n):
        if st[s] == 0:
            DFS_visit(s)
    for s in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])
     
for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        M[G[0]-1][G[2+j]-1] = 1
 
DFS()

Solution (Python):
n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()

Solution (Python):
import sys
  
def dfs(i, t, l, a, b):
   t += 1
   a[i] = t
   for j in l[i]:
      if not a[j-1]:
         t = dfs(j-1, t, l, a, b)
   t += 1
   b[i] = t
   return t
  
  
n = input()
l=[]
for i in range(n):
   l.append([int(s) for s in sys.stdin.readline().split()[2:]])
a = [0] * n
b = [0] * n
t = 0
for i in xrange(n):
   if not a[i]:
      t = dfs(i, t, l, a, b)
  
for i in xrange(n):
   print i+1, a[i], b[i]

Solution (Python):
n = int(raw_input())
  
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
tm = [0]
  
def DFS_visit(s):
  st[s] = 1
  tm[0] += 1
  d[s] = tm[0]
  for e in range(n):
    if v[s][e] == 1 and st[e] == 0:
      DFS_visit(e)
  st[s] == 2
  tm[0] += 1
  f[s] = tm[0]
  
def DFS():
  for s in range(n):
    if st[s] == 0:
      DFS_visit(s)
  for s in range(n):
     print'{0} {1} {2}'.format(s+1, d[s], f[s])
      
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
  
DFS()

Solution (Python):
n = int(raw_input())

d = [0 for i in range(n)]
f = [0 for i in range(n)]
a = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
time = [0]
G = [0 for i in range(n)]


def dfs_visit(s):
    st[s] = 1
    time[0] += 1
    d[s] = time[0]
    
    for k in range(n):  
      if a[s][k] == 1 and st[k] == 0:
          dfs_visit(k)
    st[s] ==2
    time[0] += 1
    f[s] = time[0]

def main():
    for s in range(n):
        if st[s] == 0:
            dfs_visit(s)
    for s in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])

for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        a[G[0]-1][G[2+j]-1] = 1

main()

Solution (Python):
n = int(raw_input())

d = [0 for i in range(n)]
f = [0 for i in range(n)]
a = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
time = [0]
G = [0 for i in range(n)]


def dfs_visit(s):
    st[s] = 1
    time[0] += 1
    d[s] = time[0]
    
    for k in range(n):  
      if a[s][k] == 1 and st[k] == 0:
          dfs_visit(k)
    st[s] ==2
    time[0] += 1
    f[s] = time[0]

def main():
    for s in range(n):
        if st[s] == 0:
            dfs_visit(s)
    for s in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])

for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        a[G[0]-1][G[2+j]-1] = 1

main()

Solution (Python):
n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
a = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
time = [0]
g = [0 for i in range(n)]
 
 
def dfs_visit(s):
    st[s] = 1
    time[0] += 1
    d[s] = time[0]
     
    for k in range(n):  
      if a[s][k] == 1 and st[k] == 0:
          dfs_visit(k)
    st[s] ==2
    time[0] += 1
    f[s] = time[0]
 
def main():
    for s in range(n):
        if st[s] == 0:
            dfs_visit(s)
    for s in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])
 
for i in range(n):
    g = map(int, raw_input().split())
    for j in range(g[1]):
        a[g[0]-1][g[2+j]-1] = 1
 
main()

Solution (Python):
n = int(raw_input())
  
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
t = [0]
  
def DFS_visit(s):
    st[s] = 1
    t[0] += 1
    d[s] = t[0]
    for e in range(n):
        if M[s][e] == 1 and st[e] == 0:
            DFS_visit(e)
    st[s] == 2
    t[0] += 1
    f[s] = t[0]
  
def DFS():
    for s in range(n):
        if st[s] == 0:
            DFS_visit(s)
    for s in range(n):
        print'{0} {1} {2}'.format(s+1, d[s], f[s])
      
for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        M[G[0]-1][G[2+j]-1] = 1
  
DFS()

Solution (Python):
n = int(raw_input())
t = [0]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
 
def DFS_visit(s):
	st[s] = 1
	d[s] = t[0] = t[0] + 1
	for e in range(n):
		if M[s][e] == 1 and st[e] == 0:
			DFS_visit(e)
	f[s] = t[0] = t[0] + 1
 
def DFS():
	for s in range(n):
		if st[s] == 0:
			DFS_visit(s)
	for s in range(n):
		print s+1, d[s], f[s]

for i in range(n):
	G = map(int, raw_input().split())
	for j in range(G[1]):
		M[G[0]-1][G[j+2]-1] = 1
DFS()

Solution (Python):


import sys
   
def dfs(i, t, l, a, b):
   t += 1
   a[i] = t
   for j in l[i]:
      if not a[j-1]:
         t = dfs(j-1, t, l, a, b)
   t += 1
   b[i] = t
   return t
   
   
n = input()
l=[]
for i in range(n):
   l.append([int(s) for s in sys.stdin.readline().split()[2:]])
a = [0] * n
b = [0] * n
t = 0
for i in xrange(n):
   if not a[i]:
      t = dfs(i, t, l, a, b)
   
for i in xrange(n):
   print i+1, a[i], b[i]

Solution (Python):
def depth(s, time):
    time += 1
    flag[s] = 1
    d[s] = time
    for i in range(1, n+1):
        if G[s][i] == 1:
            if flag[i] == 0:
                depth(i, time)
                time = f[i]
    f[s] = time + 1
 
n = int(raw_input())
G = [[0 for i in range(n+1)] for j in range(n+1)]
d = [0 for i in range(n+1)]
f = [0 for i in range(n+1)]
 
for i in range(n):
    v = map(int, raw_input().split())
    for j in range(v[1]):
        G[v[0]][v[2+j]] = 1
 
flag = [0 for i in range(n+1)]
for i in range(1, n+1):
    if flag[i] == 0:
        depth(i, max(f))
 
for i in range(1, n+1):
    print(str(i) + " " + str(d[i]) + " " + str(f[i]))

Solution (Python):
from __future__ import division,print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
def walk(index,tm,L,d,f):
    tm+=1
    d[index]=tm
    for i in L[index]:
        if not d[i-1]:
            tm=walk(i-1,tm,L,d,f)
    tm+=1
    f[index]=tm
    return tm
 
def main():
    num=int(sys.stdin.readline())
    L=[]
    for _ in range(num):
        L.append([int(s) for s in sys.stdin.readline().split()[2:]])
    d=[0]*num
    f=[0]*num
    tm=0
    for i in range(num):
        if not d[i]:
            tm=walk(i,tm,L,d,f)
    for i in range(num):
        print(i+1,d[i],f[i])
 
main()

Solution (Python):
n = input()

time = []
time.append(0)

d = [0 for i in xrange(n + 1)]
f = [0 for i in xrange(n + 1)]
color = ['WHITE' for i in xrange(n + 1)]

graph_map = [[0 for j in xrange(n + 1)] for i in xrange(n + 1)]

for i in xrange(1, n + 1):
    tmp = map(int, raw_input().split())
    for j in xrange(tmp[1]):
        graph_map[i][tmp[j + 2]] = 1

def dfs(u):
    color[u] = 'GRAY'
    time[0] += 1
    d[u] = time[0]
    for v in xrange(1, n + 1):
        if graph_map[u][v] == 1 and color[v] == 'WHITE':
            dfs(v)
    color[u] = 'BLACK'
    time[0] += 1
    f[u] = time[0]

for i in xrange(1, n + 1):
    if color[i] == 'WHITE':
        dfs(i)

for i in xrange(1, n + 1):
    print "%d %d %d" % (i, d[i], f[i])

Solution (Python):
n=0
m=input()
c=[0 for i in xrange(m)]
t=[0 for i in xrange(m)]


def d(u):
    global n
    if t[u]:return
    n = n + 1
    t[u]=[u+1,n]
    for i in c[u]:d(i-1)
    n = n + 1
    t[u][2:]=[n]

def dfs():
    for i in range(m):
     l=map(int,raw_input().split())
     c[l[0]-1]=l[2:]
    for i in range(m):
     d(i)
     print " ".join(map(str,t[i]))

dfs()

Solution (Python):
n=0
m=input()
c=[0 for i in xrange(m)]
ts=[0 for i in xrange(m)]


def d(u):
    global n
    if ts[u]:return
    n = n + 1
    ts[u]=[u+1,n]
    for i in c[u]:d(i-1)
    n = n + 1
    ts[u][2:]=[n]

def dfs():
    for i in range(m):
     l=map(int,raw_input().split())
     c[l[0]-1]=l[2:]
    for i in range(m):
     d(i)
     print " ".join(map(str,ts[i]))

dfs()

Solution (Python):
n=0
m=input()
c=[0 for i in xrange(m)]
ts=[0 for i in xrange(m)]


def dfs_visit(u):
    global n
    if ts[u]:return
    n = n + 1
    ts[u]=[u+1,n]
    for i in c[u]:dfs_visit(i-1)
    n = n + 1
    ts[u][2:]=[n]

def dfs():
    for i in range(m):
     l=map(int,raw_input().split())
     c[l[0]-1]=l[2:]
    for i in range(m):
     dfs_visit(i)
     print " ".join(map(str,ts[i]))

dfs()

Solution (Python):
n = int( raw_input() )
   
d = [ 0 for i in range(n) ]
f = [ 0 for i in range(n) ]
G = [ 0 for i in range(n) ]
v = [ [0 for i in range(n) ] for j in range(n) ]
st = [ 0 for i in range(n) ]
tm = [ 0 ]
   
def DFS_visit(s):
  st[ s ] = 1
  tm[ 0 ] += 1
  d[ s ] = tm[ 0 ]
  for e in range(n):
    if v[ s ][ e ] == 1 and st[ e ] == 0:
      DFS_visit(e)
  st[ s ] == 2
  tm[ 0 ] += 1
  f[ s ] = tm[ 0 ]
   
def DFS():
  for s in range(n):
    if st[ s ] == 0:
      DFS_visit(s)
  for s in range(n):
     print'{0} {1} {2}'.format( s+1 , d[ s ] , f[ s ] )
       
for i in range(n):
  G = map( int , raw_input().split() )
  for j in range( G[1] ):
    v[ G[0] -1 ][ G[ 2+j ] -1 ] = 1
   
DFS()

Solution (Python):
n = int(raw_input())
 
def dfs(u,t):
    global graph
    global found
    global timestamp
 
    if u in found: return t
    found.add(u)
    timestamp[u] = [-1,-1]
    timestamp[u][0] = t
    t += 1
    for v in graph[u]:
        t = dfs(v,t)
    timestamp[u][1] = t
    t += 1
    return t
 
graph = [[] for i in range(n)]
found = set()
timestamp = {}
 
for i in range(n):
    entry = map(int,raw_input().strip().split(' '))
    u = entry[0]
    u -= 1
    for v in entry[2:]:
        v -= 1
        graph[u].append(v)
 
 
t = 1
for i in range(n):
    t = dfs(i,t)
 
for i in timestamp:
    print i+1,timestamp[i][0],timestamp[i][1]

Solution (Python):
n = input()

d     = [0 for i in range(n)]
f     = [0 for i in range(n)]
G     = [0 for i in range(n)]
M     = [[0 for i in range(n)] for j in range(n)]
color = [0 for i in range(n)]
tt    = [0]
WHITE = 0
GRAY  = 1
BLACK = 2

def dfs_visit(u):
    color[u] = GRAY
    tt[0] = tt[0] + 1
    d[u] = tt[0]
    for v in range(n):
        if M[u][v] == 0:
            continue
        if color[v] == WHITE:
            dfs_visit(v)
    color[u] == BLACK
    tt[0] = tt[0] + 1
    f[u] = tt[0]

def dfs():
    for u in range(n):
        if color[u] == WHITE:
            dfs_visit(u)
    for u in range(n):
        print "%d %d %d" %(u + 1, d[u], f[u])


for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        M[G[0]-1][G[2+j]-1] = 1

dfs()

Solution (Python):
n = int(raw_input())
N = 100
WHITE = 0
GRAY = 1
BLACK = 2
Color = [WHITE for i in range(n)]

tt = 0
d = [0 for i in range(n)]
f = [0 for i in range(n)]
def dfs_visit(u):
    Color[u] = GRAY
    global tt
    tt += 1
    d[u] = tt
    for v in range(n):
        if M[u][v] == 0:
            continue
        if Color[v] == WHITE:
            dfs_visit(v)
    Color[u] = BLACK 
    tt += 1
    f[u] = tt
 
def dfs():
    
    tt = 0
     
    for u in range(n):
        if Color[u] == WHITE:
            dfs_visit(u)
    for u in range(n):
        print "%d %d %d" %(u + 1, d[u], f[u])
 
M = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
    tmp = map(int, raw_input().split())
    u = tmp[0]
    k = tmp[1]
    u -= 1
    for j in range(k):
        v = tmp[j + 2]
        v -= 1
        M[u][v] = 1
dfs()

Solution (Python):
n = int(raw_input())
  
d = [0 for i in range(n)]
f = [0 for i in range(n)]
a = [[0 for i in range(n)] for j in range(n)]
st = [0 for i in range(n)]
time = [0]
g = [0 for i in range(n)]
  
  
def dfs_visit(s):
    st[s] = 1
    time[0] += 1
    d[s] = time[0]
      
    for k in range(n):  
      if a[s][k] == 1 and st[k] == 0:
          dfs_visit(k)
    st[s] ==2
    time[0] += 1
    f[s] = time[0]
  
def main():
    for s in range(n):
        if st[s] == 0:
            dfs_visit(s)
    for s in range(n):
        print '%d %d %d' %(s+1, d[s], f[s])
  
for i in range(n):
    g = map(int, raw_input().split())
    for j in range(g[1]):
        a[g[0]-1][g[2+j]-1] = 1
  
main()

Solution (Python):
def visit(u):
  global t
  flag[u] = 1
  t += 1
  s[u] = t
  for v in range(n):
    if M[u][v]==0:
      continue
    if flag[v]==0:
      visit(v)
  flag[u] = 2
  t += 1
  e[u] = t


def dfs():
  for u in range(n):
    if flag[u]==0:
      visit(u)
  for u in range(n):
    print '%d %d %d' % (u+1, s[u], e[u])


n = input()
t = 0
flag = [0 for row in range(n)]
s = [0 for row in range(n)]
e = [0 for row in range(n)]
M = [[0 for col in range(n)] for row in range(n)]
for i in range(n):
  str = map(int, raw_input().split())
  u = str[0]
  k = str[1]
  a = str[2:]
  u -= 1
  for v in a:
    M[u][v-1] = 1

dfs()

Solution (Python):


from __future__ import division,print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
def walk(index,tm,L,d,f):
    tm+=1
    d[index]=tm
    for i in L[index]:
        if not d[i-1]:
            tm=walk(i-1,tm,L,d,f)
    tm+=1
    f[index]=tm
    return tm
 
def main():
    num=int(sys.stdin.readline())
    L=[]
    for _ in range(num):
        L.append([int(s) for s in sys.stdin.readline().split()[2:]])
    d=[0]*num
    f=[0]*num
    tm=0
    for i in range(num):
        if not d[i]:
            tm=walk(i,tm,L,d,f)
    for i in range(num):
        print(i+1,d[i],f[i])
 
main()

Solution (Python):
T = [0]

def curserch(N,k,T,P,n):
    T[0] = T[0]+1
    P[k]["d"] = T[0]
    for i in range(1,n+1):
        if N[k][i]==1 and P[i]["d"]==0:
            curserch(N,i,T,P,n)
            T[0] = T[0]+1
            P[i]["f"]=T[0]


n = int(input())
A = [[0 for j in range(n+1)] for i in range(n+1)]


for i in range(n):
    vec = input().split()
    u = int(vec[0])
    k = int(vec[1])
    nodes = vec[2:]
    for i in range(int(k)):
        v = int(nodes[i])
        A[u][v] = 1

P=[{"d":0} for i in range(n+1)]
for i in range(1,n+1):
    if P[i]["d"]==0:
        curserch(A,i,T,P,n)
        T[0] = T[0]+1
        P[i]["f"]=T[0]
for i in range(1,n+1):
    print(i,P[i]["d"],P[i]["f"])

Solution (Python):
n = int(raw_input())

d = [0] * n
f = [0] * n
M = [[0]*n for _ in xrange(n)]
color = [0] * n
tt = 0
WHITE = 0
GRAY = 1
BLACK = 2

def dfs_visit(u):
    global tt
    color[u] = GRAY
    tt += 1
    d[u] = tt
    for v in xrange(n):
        if M[u][v] == 0:
            continue
        if color[v] == WHITE:
            dfs_visit(v)
    color[u] = BLACK
    tt += 1
    f[u] = tt
    return 0

def dfs():
    for u in xrange(n):
        if color[u] == WHITE:
            dfs_visit(u)
    for u in xrange(n):
        print "{} {} {}".format(u+1, d[u], f[u])
    return 0

def main():
    for i in xrange(n):
        a = map(int, raw_input().split())
        u = a[0]-1
        k = a[1]
        for j in xrange(k):
            v = a[j+2] -  1
            M[u][v] = 1
    
    dfs()
    return 0

main()

Solution (Python):
from collections import deque
n = int(raw_input())

d = [0] * n
f = [0] * n
M = [[0]*n for _ in xrange(n)]
color = [0] * n
tt = 0
WHITE = 0
GRAY = 1
BLACK = 2
nt = [0] * n

def next(u):
    for v in xrange(nt[u],n):
        nt[u] = v + 1
        if M[u][v] == 1:
            return v
    return -1

def dfs_visit(r):
    global tt
    S = deque([])
    S.append(r)
    color[r] = GRAY
    tt += 1
    d[r] = tt

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

    return 0

def dfs():
    for u in xrange(n):
        if color[u] == WHITE:
            dfs_visit(u)
    for u in xrange(n):
        print "{} {} {}".format(u+1, d[u], f[u])
    
    return 0

def main():
    for i in xrange(n):
        a = map(int, raw_input().split())
        u = a[0]-1
        k = a[1]
        for j in xrange(k):
            v = a[j+2] -  1
            M[u][v] = 1
    
    dfs()
    return 0

main()

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())
mat = [[0] * n for _ in range(n)]
d, f = [0] * n, [0] * n
for _ in range(n):
    adj = list(map(int, input().split()))
    i = adj[0]
    v = adj[2:]
    for j in v:
        mat[i - 1][j - 1] = 1

time, current = 0, 0
stack = []
while 0 in f:
    if not stack:
        for i, v in enumerate(f):
            if v == 0:
                stack.append(i)
                time += 1
                d[i] = time
                break
    time += 1
    current = stack[-1]
    for i in range(len(mat[current])):
        if mat[current][i] and not d[i]:
            current = i
            d[i] = time
            stack.append(i)
            break
    else:
        f[current] = time
        current = stack.pop()

for l in zip(range(1, n + 1), d, f):
    print(*l)

Solution (Python):
def dfs(u):
    global time
    time+=1
    color[u]='gray'
    d[u]+=time
    for v in xrange(n):
        if m[u][v]!=0 and color[v]=="white":
            dfs(v)
    time+=1
    color[u]="black"
    f[u]+=time
    

n=input()
info=[0]*n
color=["white"]*n
m=[[0]*n for _ in xrange(n)]
d=[0]*n
f=[0]*n
for i in xrange(n):
    info[i]=map(int,raw_input().split())
    if info[i][1]==0:
        pass
    else:
        for j in info[i][2:]:
            m[i][j-1]=j
time=0
for i in xrange(n):
    if color[i]=="white":
        dfs(i)
for i in xrange(n):
    print i+1,d[i],f[i]

Solution (Python):
import sys

def dfs(i):
    global V, t, d, f

    if d[i] != 0:
        return

    d[i] = t
    t += 1
    for v in V[i]:
        dfs(v)

    f[i] = t
    t += 1

    return

lines = sys.stdin.readlines()
n = int(lines[0])
V = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    v = map(int, lines[i].split())
    V[v[0]] = v[2:]
d = [0] * (n + 1)
f = [0] * (n + 1)
t = 1

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

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

Solution (Python):
"""Depth First Search."""

n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)


sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])

path = []

time = 0

def dfs(u):
    global time
    path.append(u)
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)

    while path:
        u = path[-1]
        if adj[u]:
            v = adj[u].pop(0)
            if not sndf[v][0]:
                sndf[v][0] = True
                time += 1
                sndf[v].append(time)
                path.append(v)
        else:
            path.pop()
            sndf[u][0] = True
            time += 1
            sndf[u].append(time)


for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)

for x in sndf[1:]:
    print(*x[1:])

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

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)


sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])

path = []

time = 0

def dfs(u):
    global time
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)

    for v in adj[u]:
        if not sndf[v][0]:
            dfs(v)
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)


for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)

for x in sndf[1:]:
    print(*x[1:])

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

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)


sndf = [None]
for i in range(1, n + 1):
    sndf.append([False, i])

path = []

time = 0

def dfs(u):
    global time
    sndf[u][0] = True
    time += 1
    sndf[u].append(time)

    for v in adj[u]:
        if not sndf[v][0]:
            dfs(v)
    time += 1
    sndf[u].append(time)


for i in range(1, n + 1):
    if not sndf[i][0]:
        dfs(i)

for x in sndf[1:]:
    print(*x[1:])

Solution (Python):
def DFS(G):
    ans = [0] + [[0,0,0] for _ in range(len(G))]
    def main(G,i):
        ans[0] += 1
        ans[i] = [i, ans[0], ans[0]]
        for j in sorted(G[i-1][2:]):
            if ans[j][0] == 0: main(G,j)
        ans[0] += 1
        ans[i][2] = ans[0]
    for u in G:
        if ans[u[0]][0] == 0: main(G,u[0])
    return ans[1:]


if __name__=='__main__':
    n = int(input())
    G = [list(map(int,input().split())) for _ in range(n)]
    for out in DFS(G): print(*out)

Solution (Python):
class Node:
    def __init__(self,v):
        self.v = v
        self.c = []

def dfs(n,f,d,t,visited):
    visited.add(n.v)
    f[n.v] = t
    t2 = t
    for c in sorted(n.c,key=lambda x:x.v):
        if not c.v in visited:
            t2 = dfs(c,f,d,t2+1,visited)
    d[n.v] = t2+1
    return t2+1

n = int(raw_input())
nodes = {}
for _ in range(n):
    entry = map(int,raw_input().split(' '))
    nid = entry[0]
    if not nid in nodes: nodes[nid] = Node(nid)
    k = entry[1]
    if k > 0:
        children = entry[2:]
        for c in children:
            if not c in nodes: nodes[c] = Node(c)
            nodes[nid].c.append(nodes[c])

f = {}
d = {}
visited = set()
t = dfs(nodes[1],f,d,1,visited)
while len(visited) < len(nodes):
    for nid in nodes:
        if not nid in visited:
            t = dfs(nodes[nid],f,d,t+1,visited)

for k in f:
    print k,f[k],d[k]

Solution (Python):


level = False
def debug(v):
    if level:
        print(v)

n = int(input())
a = [0]

for i in range(n):
    v = input().split()
    v.pop(0)
    v.pop(0)
    a.append([int(x) for x in v])

debug(a)
stack = [1]
results = [[0 for i in range(2)] for j in range(n + 1)]
results[0][0] = 0
time = 0

def depth_first_search(a, stack):
    debug(a)
    debug(results)
    debug(stack)
    global time
    if len(stack) == 0:
        return

    v = stack.pop()
    if results[v][0] == 0:
        time += 1
        results[v][0] = time

    es = a[v]
    if len(es) == 0 and results[v][1] == 0:
        time += 1
        results[v][1] = time

    if len(es) != 0:
        stack.append(v)
        next_vert = es.pop(0)
        if results[next_vert][0] == 0:
            stack.append(next_vert)

    depth_first_search(a, stack)

for i in range(n):
    stack = [i + 1]
    depth_first_search(a, stack)

debug(results)

results.pop(0)

i = 1
for row in results:
    print(str(i) + " " + str(row[0]) + " " + str(row[1]))
    i += 1

Solution (Python):
time = 0

def dfs_visit(g, u):
    global time
    time += 1
    u[2] = time
    u[1] = 'g'

    for v in u[0]:
        ch = g[v]
        if ch[1] == 'w':
            ch[4] = u[5]
            dfs_visit(g, ch)
    u[1] = 'b'
    time += 1
    u[3] = time

n = int(input())

g = {}
s = 0
stack = []
for i in range(n):
    x = list(map(int, input().split()))
    g[x[0]] = [x[2:], 'w', 0, 0, None, x[0]]
    if i == 0:
        s = x[0]

for k, v in g.items():
    if v[1] == 'w':
        dfs_visit(g, v)


for i in range(n):
    node = g[i+1]
    print("{} {} {}".format(i+1, node[2], node[3]))

Solution (Python):



import sys

UNVISITED, VISITED_IN_STACK, POPPED_OUT = 0, 1, 2


def generate_adj(v_info):
    for v_detail in v_info:
        v_adj_list = v_detail[2:]
        assert len(v_adj_list) == int(v_detail[1])
        for each in v_adj_list:
            init_adj_matrix[int(v_detail[0]) - 1][int(each) - 1] = 1
    return init_adj_matrix


def graph_dfs(v_init):
    global time
    
    vertex_visit_stack.append(v_init)
    vertex_status_list[v_init] = VISITED_IN_STACK
    vertex_d_time[v_init] += time
    
    while len(vertex_visit_stack) > 1:
        current_vertex = vertex_visit_stack[-1]
        next_vertex = get_adj_vertices(_vertex=current_vertex)
        

        if next_vertex:
            if vertex_status_list[next_vertex] is UNVISITED:
                vertex_status_list[next_vertex] = VISITED_IN_STACK
                time += 1
                vertex_d_time[next_vertex] += time
                vertex_visit_stack.append(next_vertex)
                
        else:
            
            vertex_visit_stack.pop()
            vertex_status_list[current_vertex] = POPPED_OUT
            time += 1
            vertex_f_time[current_vertex] += time
        

    return None


def get_adj_vertices(_vertex):
    for j in range(vertex_num):
        if adj_matrix[int(_vertex) - 1][j]:
            adj_matrix[int(_vertex) - 1][j] = 0
            return j + 1
    return None


def dfs_start():
    global time
    for i in range(vertex_num):
        if vertex_status_list[i + 1] == UNVISITED:
            
            graph_dfs(v_init=i + 1)
            time += 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertex_num = int(_input[0])
    vertex_info = list(map(lambda x: x.split(), _input[1:]))
    init_adj_matrix = [[0] * vertex_num for _ in range(vertex_num)]
    
    
    vertex_visit_stack = [-1]
    vertex_status_list = [UNVISITED] * vertex_num
    vertex_status_list.insert(0, -1)
    vertex_d_time, vertex_f_time = ([0] * (vertex_num + 1) for _ in range(2))

    adj_matrix = generate_adj(vertex_info)

    time = 1
    dfs_start()

    for k in range(vertex_num):
        print(k + 1, vertex_d_time[k + 1], vertex_f_time[k + 1])