Depth First Search

raw_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.

solutions: ["import heapq\nfrom collections import deque\nfrom enum import Enum\nimport sys\nimport math\nfrom _heapq import heappush, heappop\n\nBIG_NUM = 2000000000\nMOD = 1000000007\nEPS = 0.000000001\n\nglobal current_time\nglobal visited,go_time,back_time\nglobal G\n\n\ndef dfs(node_id):\n    global current_time #\u66f8\u304b\u306a\u3044\u3068\u30ed\u30fc\u30ab\u30eb\u5909\u6570\u6271\u3044\u3055\u308c\u308b\n    go_time[node_id] = current_time\n    current_time += 1\n\n    for next_node in G[node_id]:\n\n        if visited[next_node] == True:\n            continue\n        visited[next_node] = True\n        dfs(next_node)\n\n    back_time[node_id] = current_time\n    current_time += 1\n\n\nV = int(input())\n\nG = [[] for i in range(V)]\n\nvisited = [False]*V\n\ngo_time = [0]*V\nback_time = [0]*V\n\nfor loop in range(V):\n    node_id,num,*tmp_adj = list(map(int,input().split()))\n    node_id -= 1\n    for i in range(num):\n        G[node_id].append(tmp_adj[i]-1)\n\ncurrent_time = 1;\n\nfor i in range(V):\n    if visited[i] == True:\n        continue\n    visited[i] = True\n    dfs(i)\n\nfor i in range(V):\n    print(\"%d %d %d\"%(i+1,go_time[i],back_time[i]))\n\n\n\n\n", "import sys\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\n\nN = int(readline())\nG = [None]*(N+1)\nfor i in range(N):\n    u, k, *vs = map(int, readline().split())\n    G[u] = vs\n\n\nbegin = [-1]*(N+1)\nend = [-1]*(N+1)\nlb = iter(range(1, 2*N+1)).__next__\ndef dfs(v):\n    begin[v] = lb()\n    for w in G[v]:\n        if begin[w] != -1:\n            continue\n        dfs(w)\n    end[v] = lb()\n\n\nfor v in range(1, N+1):\n    if begin[v] != -1:\n        continue\n    dfs(v)\nwrite(\"\\n\".join(\"{} {} {}\".format(*args) for args in zip(range(1, N+1), begin[1:], end[1:])))\nwrite(\"\\n\")\n\n", "from collections import defaultdict\nimport sys\n\nsys.setrecursionlimit(10**6)\n\ndef dfs(curr):\n    global t\n    S[curr] = t\n    visited.add(curr)\n    for np in nei_dict[curr]:\n        if np in visited:\n            continue\n        t += 1\n        dfs(np)\n    t += 1\n    F[curr] = t\n\nn = int(input())\nnei_dict = defaultdict(list)\nfor i in range(n):\n    lst = list(map(int, input().split()))\n    k = lst[1]\n    lst = lst[2:]\n    for j in range(k):\n        nei_dict[i].append(lst[j] - 1)\n\nS = [0 for _ in range(n)]\nF = [0 for _ in range(n)]\nvisited = set()\nt = 1\nfor i in range(n):\n    if i not in visited:\n        dfs(i)\n        t += 1\nfor i in range(n):\n    print(i + 1, S[i], F[i])\n\n", "import sys\n\n# READ_FROM_FILE = True\nREAD_FROM_FILE = False\n\nnum_vertexes = 0\nadjacency_list = []\ncurrent_time = 0\nis_visited = []\nfound_time = []\nsearch_finished_time = []\n\n\ndef dfs(v):\n    global current_time\n    if is_visited[v]:\n        return\n    found_time[v] = current_time\n    is_visited[v] = True\n    current_time += 1\n\n    for u in adjacency_list[v]:\n        if is_visited[u]:\n            continue\n        dfs(u)\n    search_finished_time[v] = current_time\n    current_time += 1\n    return\n\n\ndef main():\n    if READ_FROM_FILE:\n        f = open('test0.txt', 'r')\n    else:\n        f = sys.stdin\n\n    global num_vertexes, found_time, search_finished_time, adjacency_list, is_visited, current_time\n    num_vertexes = int(f.readline())\n    found_time = [0] * num_vertexes\n    search_finished_time = [0] * num_vertexes\n    is_visited = [False] * num_vertexes\n\n    adjacency_list = [[] for _ in range(num_vertexes)]\n    for _ in range(num_vertexes):\n        adjacency = list(map(int, f.readline().split()))\n        cn = adjacency[0] - 1\n        adjacency = adjacency[2:]\n        for i in range(len(adjacency)):\n            adjacency[i] -= 1\n        adjacency_list[cn] += adjacency\n\n    current_time = 1\n    for i in range(num_vertexes):\n        dfs(i)\n\n    for i in range(num_vertexes):\n        print(i + 1, found_time[i], search_finished_time[i])\n\n    if READ_FROM_FILE:\n        f.close()\n    return\n\n\nif __name__ == '__main__':\n    main()\n\n", "n = int(input())\nG = []\nchecked = [False for i in range(n + 1)]\nd = [0 for i in range(n + 1)]\nf = [0 for i in range(n + 1)]\nG.append([])\nfor i in range(n):\n    u, k, *v = map(int, input().split())\n    G.append(v)\n\ntimestamp = 1\n\ndef dfs(id):\n    global timestamp\n\n    checked[id] = True\n    d[id] = timestamp\n    timestamp += 1\n    for v in G[id]:\n        if not checked[v]:\n            dfs(v)\n    f[id] = timestamp\n    timestamp += 1\n\nfor id in range(1, n + 1):\n    if not checked[id]:\n        dfs(id)\n\nfor i in range(1, n + 1):\n    print(\"{0} {1} {2}\".format(i, d[i], f[i]))\n", "n = int(input())\ng = [[] for _ in range(n)]\n\nfor i in range(n):\n    u, k, *a = map(int, input().split())\n    g[u - 1] = a\n\nIN = [0 for _ in range(n)]\nOUT = [0 for _ in range(n)]\n\nglobal t\ndef dfs(u):\n    global t\n    t += 1\n    IN[u] = t\n    visited[u] = True\n    for e in g[u]:\n        if visited[e - 1] == False:\n            dfs(e - 1)\n    t += 1\n    OUT[u] = t\n\nvisited = [0 for _ in range(n)]\nt = 0\nfor i in range(n):\n    if visited[i] == True:\n        continue\n    dfs(i)\n\nfor i in range(n):\n    print(i + 1, IN[i], OUT[i])\n", "# \u6df1\u3055\u512a\u5148\u63a2\u7d22\ndef dfs(a, n_, r, u_):\n    if r[u_][0] == 0:\n        r[u_][0] = 1\n        r[u_][2] = dfs.count\n        dfs.count += 1\n    for j in range(n_):\n        if a[u_][j] == 1:\n            if r[j][0] == 0:\n                dfs(a, n_, r, j)\n    if r[u_][1] == 0:\n        r[u_][1] = 1\n        r[u_][3] = dfs.count\n        dfs.count += 1\n\n\ndfs.count = 1\nn = int(input())\n\nadj = [[0 for _ in range(n)] for _ in range(n)]\n\nfor _ in range(n):\n    u = list(map(int, input().split()))\n    for i in range(u[1]):\n        adj[u[0] - 1][u[2 + i] - 1] = 1\n\nresult = [[0] * 4 for _ in range(n)]\nfor i in range(n):\n    dfs(adj, n, result, i)\n\nfor i in range(n):\n    print(i + 1, result[i][2], result[i][3])\n\n", "n = int(input())\n\nadj = [None]\nfor i in range(n):\n    adj_i = list(map(int, input().split()[2:]))\n    adj.append(adj_i)\n\n# searched or not, number of vertex, discovery time and finishing time.\nsndf = [None]\nfor i in range(1, n + 1):\n    sndf.append([False, i])\n\npath = []\n\ntime = 0\n\ndef dfs(u):\n    global time\n    sndf[u][0] = True\n    time += 1\n    sndf[u].append(time)\n\n    for v in adj[u]:\n        if not sndf[v][0]:\n            dfs(v)\n    time += 1\n    sndf[u].append(time)\n\n\nfor i in range(1, n + 1):\n    if not sndf[i][0]:\n        dfs(i)\n\nfor x in sndf[1:]:\n    print(*x[1:])\n", "from sys import stdin\n\nd_num = int(stdin.readline().strip())\n\ngraph = [[] for _ in range(d_num+1)]\nfor _ in range(d_num):\n    u, k, *neighbors = map(int, stdin.readline().split())\n    for v in neighbors:\n        graph[u].append(v)\n\nvisited = set()\ntimestamps = [None for _ in range(d_num+1)]\n\ndef dfs(u, stmp):\n    visited.add(u)\n    entry = stmp\n\n    stmp += 1\n    for v in graph[u]:\n        if v not in visited:\n            stmp = dfs(v, stmp)\n\n    timestamps[u] = entry, stmp\n    return stmp+1\n\nstmp = 1\nfor v in range(1, d_num+1):\n    if v not in visited: stmp = dfs(v, stmp)\n\nfor num, (entry, leave) in enumerate(timestamps[1:], 1):\n    print(num, entry, leave)\n", "#!usr/bin/env python3\nfrom collections import defaultdict,deque\nfrom heapq import heappush, heappop\nfrom itertools import permutations\nimport sys\nimport math\nimport bisect\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef I(): return int(sys.stdin.readline())\ndef LS():return [list(x) for x in sys.stdin.readline().split()]\ndef S():\n    res = list(sys.stdin.readline())\n    if res[-1] == \"\\n\":\n        return res[:-1]\n    return res\ndef IR(n):\n    return [I() for i in range(n)]\ndef LIR(n):\n    return [LI() for i in range(n)]\ndef SR(n):\n    return [S() for i in range(n)]\ndef LSR(n):\n    return [LS() for i in range(n)]\n\nsys.setrecursionlimit(1000000)\nmod = 1000000007\n\ncnt = 1\ndef solve():\n    global cnt\n    def dfs(x):\n        global cnt\n        f[x] = cnt\n        for y in v[x]:\n            if not d[y]:\n                d[y] = cnt\n                cnt += 1\n                dfs(y)\n        f[x] = cnt\n        cnt += 1\n\n    n = I()\n    v = []\n    for i in range(n):\n        e = LI()\n        u = e[2:]\n        for i in range(len(u)):\n            u[i] -= 1\n        v.append(u)\n    d = [0]*n\n    f = [0]*n\n    for i in range(n):\n        if not d[i]:\n            d[i] = cnt\n            cnt += 1\n            dfs(i)\n    for i in range(n):\n        print(i+1,d[i],f[i])\n    return\n\n#Solve\nif __name__ == \"__main__\":\n    solve()\n\n", "def d(u):\n global t\n C[u]=1;D[u]=t;t+=1\n for v in M[u]:v=int(v)-1;C[v]or d(v)\n F[u]=t;t+=1\nN=int(input());R=range(N)\nM=[input().split()[2:]for _ in R]\nC,D,F=[0]*N,[0]*N,[0]*N\nt=1\nfor i in R:C[i]or d(i)\nfor i in R:print(i+1,D[i],F[i])\n", "def dfs(num, lst, d, f, cnt):\n    if d[num] != 0:\n        return cnt - 1\n    d[num] = cnt\n    for n in lst[num]:\n        cnt += 1\n        cnt = dfs(n - 1, lst, d, f ,cnt)\n    cnt += 1\n    f[num] = cnt\n    return cnt\n\n\nn = int(input())\nd = [0 for i in range(n)]\nf = [0 for i in range(n)]\nlst = []\nfor _ in range(n):\n    n = list(map(int, input().split()))\n    lst.append(n[2:])\n\ncnt = 1\nwhile 0 in d:\n    num = d.index(0)\n    cnt = dfs(num, lst, d, f, cnt) + 1\n\nfor i, j in enumerate(zip(d, f)):\n    print(i + 1, j[0], j[1])\n", "import sys\nsys.setrecursionlimit(10**8) # \u518d\u8d77\u56de\u6570\u306e\u8a2d\u5b9a\nN = int(input())\nukv = [list(map(int, input().split())) for _ in range(N)]\nd = [0]*(N+1)\nf = [0]*(N+1)\nnow = 1\ndef dfs(x):\n    global now\n    d[x] = now\n    now += 1\n    for i in range(ukv[x-1][1]):\n        if(d[ukv[x-1][2+i]]!=0):\n            continue\n        dfs(ukv[x-1][2+i])\n    f[x] = now\n    now += 1\n    return\nfor i in range(N):\n    if(d[i+1]==0):\n        dfs(i+1)\nfor i in range(N):\n    print(i+1, d[i+1], f[i+1])\n", "# \u6df1\u3055\u512a\u5148\u63a2\u7d22\n\nimport sys\n\nsys.setrecursionlimit(100000)\n\ntime = 0\ndef dfs(v,d,f,G,check):\n    global time\n    if check[v] == True:\n        return\n    time += 1\n    d[v] = time\n    check[v] = True\n    for to in sorted(G[v]):\n        if check[to] == False:\n            dfs(to, d,f,G,check)\n    \n    time += 1\n    f[v] = time\n    return \n\n\ndef main():\n    n = int(input())\n    d = [0]*n\n    f = [0]*n\n    G = [[] for _ in range(n)]  \n    check = [False]*n\n    for i in range(n):\n        pt = list(map(int, input().split()))\n        for j in range(pt[1]):\n            G[pt[0]-1].append(pt[2+j]-1)\n    \n    for i in range(n):\n        if check[i] == True:\n            continue\n        dfs(i,d,f,G,check)\n    \n    for i in range(n):\n        print(i+1,d[i],f[i])\n\n    \n\nif __name__ == '__main__':\n    main()\n\n", "def dfs(v, cnt):\n    D[v] = cnt\n    cnt += 1\n    for c in edge[v]:\n        if D[c] == -1:\n            cnt = dfs(c, cnt)\n    F[v] = cnt\n    cnt += 1\n    return cnt\n\n\nV = int(input())\nedge = [[] for _ in range(V)]\nfor _ in range(V):\n    u, _, *v = map(lambda x: int(x)-1, input().split())\n    edge[u] = sorted(v)\nD, F = [-1] * V, [-1] * V\nc = 1\nfor i in range(V):\n    if D[i] == -1:\n        c = dfs(i, c)\nfor i, (d, f) in enumerate(zip(D, F)):\n    print(i+1, d, f)\n", "n = int(input())\nl = [[] for i in range(n)]\n\n\nclass V:\n    def __init__(self, node):\n        self.d = -1\n        self.f = -1\n        self.node = node\n\n\nfor i in range(n):\n    _input = [int(j) - 1 for j in input().split(\" \")]\n    u = _input[0]\n    k = _input[1] + 1\n    node = sorted(_input[2::])\n    if u in node:\n        node.remove(u)\n    l[u] = V(node)\n\ntime = 1\n\n\ndef DFS(i):\n    global time\n    if l[i].d == -1:\n        l[i].d = time\n    time += 1\n    for n in l[i].node:\n        if l[n].d == -1:\n            DFS(n)\n            time+=1\n    if l[i].f == -1:\n        l[i].f = time\n    return\n\n\nfor i in range(n):\n    if l[i].d == -1:\n        DFS(i)\n        time+=1\n\nfor i, v in enumerate(l):\n    print(i + 1, v.d, v.f)\n\n", "# Input:\n#     - i:\u73fe\u5728\u3044\u308b\u9802\u70b9\u306e\u756a\u53f7\n# Description:\n#     - DFS\u3092\u884c\u3044\u3001\u5404\u9802\u70b9\u306e\u767a\u898b\u6642\u523b\u3001\u5b8c\u4e86\u6642\u523b\u3092\u8a18\u9332\u3059\u308b\ndef dfs(i):\n    global t # t\u3092\u30b0\u30ed\u30fc\u30d0\u30eb\u5909\u6570\u3068\u5ba3\u8a00\n    for j in g[i]: # i\u304b\u3089\u79fb\u52d5\u3067\u304d\u308b\u5168\u3066\u306e\u9802\u70b9j\u306b\u3064\u3044\u3066\u7e70\u308a\u8fd4\u3057\n        if d[j] == -1: # j\u304c\u672a\u767a\u898b\u3067\u3042\u308b\u5834\u5408\n            t += 1 # \u6642\u523b\u30921\u9032\u3081\u308b\n            d[j] = t # j\u306e\u767a\u898b\u6642\u523b\u3092\u8a18\u9332\n            dfs(j) # j\u306b\u79fb\u52d5\n    t += 1 # \u6642\u523b\u30921\u9032\u3081\u308b\n    f[i] = t # i\u306e\u5b8c\u4e86\u6642\u523b\u3092\u8a18\u9332\u3059\u308b\n    return \n\nn = int(input()) # \u9802\u70b9\u6570n\u3092\u5165\u529b\ng = [[] for i in range(n+1)] # \u96a3\u63a5\u30ea\u30b9\u30c8\u3092\u8868\u308f\u3059\u914d\u5217\u3092\u7528\u610f\nfor i in range(n): # n\u56de\u7e70\u308a\u8fd4\u3057\n    l = list(map(int,input().split())) # \u9802\u70b9\u306e\u60c5\u5831\u3092\u5165\u529b\n    if l[1] > 0: # l[0]\u304b\u3089\u79fb\u52d5\u3067\u304d\u308b\u9802\u70b9\u304c\u5b58\u5728\u3059\u308b\u5834\u5408\n        g[l[0]] = l[2:] # \u96a3\u63a5\u30ea\u30b9\u30c8\u3092g\u306b\u4fdd\u5b58\n\nd = [-1]*(n+1) # \u767a\u898b\u6642\u523b\u3092\u8868\u308f\u3059\u914d\u5217\u3092\u7528\u610f\nf = [-1]*(n+1) # \u5b8c\u4e86\u6642\u523b\u3092\u8868\u308f\u3059\u914d\u5217\u3092\u7528\u610f\nt = 0 # \u73fe\u5728\u306e\u6642\u523b\u3092\u8868\u308f\u3059\u5909\u6570t\u30920\u3067\u521d\u671f\u5316\nfor i in range(1,n+1): # 1\u304b\u3089n\u307e\u3067\u7e70\u308a\u8fd4\u3057\n    if d[i] == -1: # i\u304c\u672a\u767a\u898b\u306e\u5834\u5408\n        t += 1 # \u6642\u523b\u30921\u9032\u3081\u308b\n        d[i] = t # i\u306e\u767a\u898b\u6642\u523b\u3092\u8a18\u9332\n        dfs(i) # i\u304b\u3089DFS\u3092\u884c\u3046\n\nfor i in range(1,n+1): # 1\u304b\u3089n\u307e\u3067\u7e70\u308a\u8fd4\u3057\n    print(i,d[i],f[i]) # i\u306e\u767a\u898b\u6642\u523b\u3001\u5b8c\u4e86\u6642\u523b\u3092\u51fa\u529b\n", "#!/usr/bin/env python3\n\nimport sys\nimport math\nfrom bisect import bisect_right as br\nfrom bisect import bisect_left as bl\nsys.setrecursionlimit(10**8)\nfrom heapq import heappush, heappop,heappushpop\nfrom collections import defaultdict\nfrom itertools import accumulate\nfrom collections import Counter\nfrom collections import deque\nfrom operator import itemgetter\nfrom itertools import permutations\nmod = 10**9 + 7\ninf = float('inf')\ndef I(): return int(sys.stdin.readline())\ndef LI(): return list(map(int,sys.stdin.readline().split()))\n\ndef dfs(v, p, t, s, g, f):\n    if s[v] == 0:\n        s[v] = t\n        t += 1\n    for u in edges[v]:\n        if u != p and s[u] == 0:\n            t, s, g, f = dfs(u, v, t, s, g, f)\n    if g[v] == 0:\n        g[v] = t\n        t += 1\n        f[v] = True\n    return t, s, g, f\n\nn = I()\nedges = [[] for _ in range(n)]\nfor _ in range(n):\n    info = LI()\n    u = info[0]\n    for v in info[2:]:\n        edges[u-1].append(v-1)\n\ns = [0]*n\ng = [0]*n\nflag = [False]*n\nt = 1\nv = 0\nwhile 1:\n    for i in range(n):\n        if not flag[i]:\n            v = i\n            break\n    else:\n        break\n    t, s, g, flag = dfs(v, -1, t, s, g, flag)\n\nfor i in range(n):\n    print(i+1, s[i], g[i])\n\n", "from enum import Enum\n\n\nclass Dfs(object):\n    \"\"\" Depth First Search \"\"\"\n    class Status(Enum):\n        white = 1\n        gray = 2\n        black = 3\n\n    def __init__(self, data):\n        self.time = 0\n        num_of_nodes = len(data)+1\n        self.color = [Dfs.Status.white] * (num_of_nodes+1)\n        self.S = []\n        self.M = self._make_matrix(data)\n        self.s_time = [0] * (len(data) + 1)\n        self.f_time = [0] * (len(data) + 1)\n\n    def _make_matrix(self, data):\n        \"\"\" ??\u00a3??\\??????????????? (M[i][j]?????\u00a2??\u00a7??????????????????+1??????????????????????????????) \"\"\"\n        num = len(data)\n        graph_table = [[0] * (num+1) for _ in range(num+1)]\n        for d in data:\n            node_id = d[0]\n            num_of_e = d[1]\n            for e in d[2:]:\n                graph_table[node_id][e] = 1\n        return graph_table\n\n    def search(self, start):\n        self.time += 1\n        self.s_time[start] = self.time\n        self.S.append(start)\n        self.color[start] = Dfs.Status.gray\n\n        while self.S:\n            u = self.S[-1]\n            v = self.next(u)\n            if v != None:\n                if self.color[v] == Dfs.Status.white:\n                    self.color[v] = Dfs.Status.gray\n                    self.time += 1\n                    self.s_time[v] = self.time\n                    self.S.append((v))\n            else:\n                self.S = self.S[:-1]\n                self.color[u] = Dfs.Status.black\n                self.time += 1\n                self.f_time[u] = self.time\n\n    def next(self, node):\n        \"\"\" ?\u00ac?????\u00a8???????????\u00b1???????????????????????????????????????????????\u00a8??????????????????????????????? \"\"\"\n        edges = self.M[node]\n        for i in range(1, len(edges)):\n            if edges[i] == 1:\n                if self.color[i] == Dfs.Status.white:\n                    return i\n        return None\n\n    def print(self):\n        for r in self.M:\n            print(*r)\n\n\nif __name__ == '__main__':\n    # ??????????????\\???\n    num = int(input())\n    data = []\n    for _ in range(num):\n        data.append(list(map(int, input().split(' '))))\n\n    # ???????????????\n    d = Dfs(data)\n    for i in range(1, num+1):\n        if d.color[i] == Dfs.Status.white:\n            d.search(i)\n\n    # ???????????????\n    for i in range(1, num+1):\n        print('{0} {1} {2}'.format(i, d.s_time[i], d.f_time[i]))\n", "n = int(input())\nikeru = [[] for i in range(n)]\nfor i in range(n):\n\tt = list(map(int,input().split()))\n\tfor j in t[2:]:\n\t\tikeru[t[0]-1].append(j-1)\n\n#\u3053\u3053\u304b\u3089DFS\ntansaku = [0] * n\n\nf = [0] * n\ng = [0] * n\n\ntime = 0\n\nfor i in range(n):\n\tif tansaku[i]:\n\t\tcontinue\n\tmada = [~i, i] #\u63a2\u7d22\u3059\u308b\u5019\u88dc.\n\t\n\twhile mada:\n\t\ti = mada.pop() #mada\u306e\u53f3\u7aef\u3092\u53d6\u308a\u51fa\u3059\n\t\tif i >= 0 and tansaku[i] == 1:\n\t\t\tcontinue\n\t\ttime += 1\n\t\tif i >= 0:\n\t\t\ttansaku[i] = 1\n\t\t\tf[i] = time\n\t\t\tfor j in reversed(ikeru[i]):\n\t\t\t\tif tansaku[j] == 0:\n\t\t\t\t\tmada.append(~j)\n\t\t\t\t\tmada.append(j)\n\t\telse:\n\t\t\tif g[~i] == 0:\n\t\t\t\tg[~i] = time\n\t\t\telse:\n\t\t\t\ttime -= 1\n\t\t\t\nfor i in range(n):\n\tprint(i+1, f[i], g[i])\n", "N = int(input())\nadj = [[] for _ in range(N + 1)]\nfor _ in range(N):\n    u, k, *v = map(int, input().split())\n    adj[u] = v\nd = [None for _ in range(N + 1)]\nf = [None for _ in range(N + 1)]\ncount = 0\n\n\ndef dfs(v):\n    global count\n    count += 1\n    d[v] = count\n    for dest in adj[v]:\n        if d[dest] is None:\n            dfs(dest)\n    count += 1\n    f[v] = count\n\n\nfor i in range(1, N + 1):\n    if d[i] is None:\n        dfs(i)\nfor i in range(1, N + 1):\n    print(i, d[i], f[i])\n\n", "def depth_search(i, adj, d, f, t):\n    if d[i - 1]:\n        return t\n    d[i - 1] = t\n    t += 1\n    for v in adj[i - 1]:\n        t = depth_search(v, adj, d, f, t)\n    f[i - 1] = t\n    t += 1\n    return t\nn = int(input())\nadj = [list(map(int, input().split()))[2:] for _ in range(n)]\n\nd = [0] * n\nf = [0] * n\n\nt = 1\nfor i in range(n):\n    if d[i] == 0:\n        t = depth_search(i + 1, adj, d, f, t)\n\nfor i, df in enumerate(zip(d, f)):\n    print(i + 1, *df)   \n", "n = int(input())\n\nedge = [[] for _ in range(n)]\nfor _ in range(n):\n    i, k, *arg = map(lambda x: int(x) - 1, input().split())\n    for a in arg:\n        edge[i].append(a)\n\nlogs = [[] for _ in range(n)]\ncnt = 0\n\ndef dfs(now, old = -1):\n    global logs, cnt\n    if len(logs[now]) == 0:\n        cnt += 1\n        logs[now].append(cnt)\n    \n    for to in edge[now]:\n        if to == old:\n            continue\n        elif logs[to]:\n            continue\n        else:\n            dfs(to, now)\n    \n    if len(logs[now]) == 1:\n        cnt += 1\n        logs[now].append(cnt)\n\nfor i in range(n):\n    if logs[i]:\n        continue\n    \n    dfs(i)\n\nfor i in range(n):\n    print(i + 1, *logs[i])\n\n", "\nd = None\nf = None\n\n\ndef dfs(g, cur, time):\n    global d, f\n    d[cur] = time\n    for next in g[cur]:\n        if d[next] == 0:\n            time = dfs(g, next, time+1)\n    f[cur] = time + 1\n    return time + 1\n\n\ndef main():\n    global d, f\n    n = int(input())\n    g = [[] for _ in range(n)]\n    d = [0 for _ in range(n)]\n    f = [0 for _ in range(n)]\n    for _ in range(n):\n        inp = list(map(int, input().split()))\n        m = inp[0] - 1\n        k = inp[1]\n        for i in range(k):\n            g[m].append(inp[i+2] - 1)\n    time = 1\n    for i in range(n):\n        if d[i] == 0:\n            time = dfs(g, i, time) + 1\n    for i in range(n):\n        print(i+1, d[i], f[i])\n\n\nif __name__ == '__main__':\n    main()\n\n", "N = int(input())\n\nE = [None] * (N+1)\nfor _ in range(N):\n    u, k, *vs = list(map(int, input().split()))\n    E[u] = vs\n\nd = [0] * (N+1)\nf = [0] * (N+1)\nt = 0\n\ndef dfs(v):\n    global t, d, f\n    if d[v]:\n        return\n    t += 1\n    d[v] = t\n    for u in E[v]:\n        dfs(u)\n    t += 1\n    f[v] = t\n\nfor v in range(1, N+1):\n    dfs(v)\n\nfor v in range(1, N+1):\n    print(v, d[v], f[v])\n", "# Python\u3067\u63d0\u51fa\uff01\uff01\nimport sys\nsys.setrecursionlimit(10**7)\n\ndef dfs(s):\n    global cnt\n\n    cnt += 1\n    stamp[s][0] = cnt\n\n    seen[s] = True\n\n    for to in graph[s]:\n        if seen[to]:\n            continue\n        dfs(to)\n\n    cnt += 1\n    stamp[s][1] = cnt    \n\nN =int(input())\ngraph = [[]]\nfor _ in range(N):\n    u,k,*v =map(int,input().split())\n    graph.append(v)\n\nstamp = [[0,0] for _ in range(N+1)]\nseen = [False]*(N+1)\ncnt = 0\n\nfor i in range(1,N+1):\n    if not seen[i]:\n        dfs(i)\n\nfor i,a in enumerate(stamp[1:]):\n    print(i+1, *a)\n", "n = int(input())\nG = [[] for _ in range(n)]\n\ndef search(i, G, searched, s_ts, e_ts, current_ts):\n    if i in searched: return current_ts\n    \n    searched.append(i)\n    s_ts[i] = current_ts\n    current_ts += 1\n    \n    for g in G[i]:\n        current_ts = search(g - 1, G, searched, s_ts, e_ts, current_ts)\n    \n    e_ts[i] = current_ts\n    current_ts += 1\n    \n    return current_ts\n\nfor _ in range(n):\n    s = list(map(int, input().split()))\n    u, k = s[:2]\n    v = s[2:]\n    v. sort()\n    \n    G[u - 1] = v\n\ns_ts = [0 for _ in range(n)]\ne_ts = [0 for _ in range(n)]\ncurrent_ts = 1\n\nsearched = []\n\nfor i in range(n):\n    current_ts = search(i, G, searched, s_ts, e_ts, current_ts)\n\nfor i in range(n):\n    print(f\"{i + 1} {s_ts[i]} {e_ts[i]}\")\n", "class DFS:\n\tdef __init__(self, n):\n\t\tself.G = [[] for _ in range(n)]\n\t\tself.used = [False] * n\n\t\tself.ts = [None] * n\n\tdef add_edge(self, u, v):\n\t\tself.G[u].append(v)\n\tdef dfs(self, u, time):\n\t\tself.used[u] = True\n\t\ttime += 1\n\t\tself.ts[u] = (time, -1)\n\t\tfor v in self.G[u]:\n\t\t\tif not self.used[v]:\n\t\t\t\ttime = self.dfs(v, time)\n\t\ttime += 1\n\t\tself.ts[u] = (self.ts[u][0], time)\n\t\treturn time\n\nn = int(input())\ndfs = DFS(n)\nfor _ in range(n):\n\tv = list(map(int, input().split(\" \")))\n\ti = v[0]\n\tfor j in v[2:]:\n\t\tdfs.add_edge(i-1, j-1)\ntime = 0\nwhile not all(dfs.used):\n\ti = dfs.used.index(False)\n\ttime = dfs.dfs(i, time)\n\nfor i, (ts, te) in enumerate(dfs.ts):\n\tprint(i+1, ts, te)\n", "n = int(input())\ng = [None] * n\nvisited = [0] * n\nroot = set(range(n))\nts = [[0, 0] for _ in range(n)]\nt = 0\n\nwhile n:\n    l = list(map(int, input().split()))\n    connected = [i - 1 for i in l[2:]]\n    g[l[0] - 1] = [i - 1 for i in l[2:]]\n    root -= set(connected)\n    n -= 1\n\n\ndef dfs(i):\n    global g, t, ts, visited\n    lts = ts[i]\n    t += 1\n    lts[0] = t\n    visited[i] = 1\n    for c in g[i]:\n        if not visited[c]:\n            dfs(c)\n    t += 1\n    lts[1] = t\n\nif root:\n    for r in sorted(root):\n        dfs(r)\nelse:\n    dfs(0)\n\nfor i, v in enumerate(ts):\n    print(i + 1, *v)\n", "import abc\n\n\nclass AdjacentGraph:\n    \"\"\"Implementation adjacency-list Graph.\n    Beware ids are between 1 and size.\n    \"\"\"\n    def __init__(self, size):\n        self.size = size\n        self._nodes = [[0] * (size+1) for _ in range(size+1)]\n\n    def set_adj_node(self, id_, adj_id):\n        self._nodes[id_][adj_id] = 1\n\n    def __iter__(self):\n        self._id = 0\n        return self\n\n    def __next__(self):\n        if self._id < self.size:\n            self._id += 1\n            return (self._id, self._nodes[self._id][1:])\n\n        raise StopIteration()\n\n    def dfs(self, handler=None):\n\n        visited = []\n        while len(visited) < self.size:\n            for id_ in range(1, self.size+1):\n                if id_ not in visited:\n                    stack = [(id_, 0)]\n                    break\n            while len(stack) > 0:\n                i, j = stack.pop()\n                if j == 0:\n                    if handler:\n                        handler.visit(i)\n                    visited.append(i)\n                    yield i\n                try:\n                    j = self._nodes[i].index(1, j+1)\n                    stack.append((i, j))\n                    if j not in visited:\n                        stack.append((j, 0))\n                except ValueError:\n                    if handler:\n                        handler.leave(i)\n\n\nclass EventHandler(abc.ABC):\n    @abc.abstractmethod\n    def visit(self, i):\n        pass\n\n    @abc.abstractmethod\n    def leave(self, i):\n        pass\n\n\nclass Logger(EventHandler):\n    def __init__(self, n):\n        self.log = [(0, 0)] * n\n        self.step = 0\n\n    def visit(self, i):\n        self.step += 1\n        self.log[i-1] = (self.step, 0)\n\n    def leave(self, i):\n        self.step += 1\n        (n, m) = self.log[i-1]\n        self.log[i-1] = (n, self.step)\n\n    def by_node(self):\n        i = 1\n        for discover, finish in self.log:\n            yield (i, discover, finish)\n            i += 1\n\n\ndef run():\n    n = int(input())\n    g = AdjacentGraph(n)\n    log = Logger(n)\n\n    for i in range(n):\n        id_, c, *links = [int(x) for x in input().split()]\n        for n in links:\n            g.set_adj_node(id_, n)\n\n    for i in g.dfs(log):\n        pass\n\n    for node in log.by_node():\n        print(\" \".join([str(i) for i in node]))\n\n\nif __name__ == '__main__':\n    run()\n\n", "import sys\nsys.setrecursionlimit(10**6)\np = 0\ndef saiki(z):\n    global p\n    \n    #if rp[z][0] == 0:\n    rp[z][0] = p\n    for i in range(len(mp[z])):\n        if rp[mp[z][i]][0] == 0:\n            p += 1\n            saiki(mp[z][i])\n    p += 1\n    rp[z][1] = p\nn = int(input())\nmp = [[] for i in range(n)]\nrp = [[0 for i in range(2)] for j in range(n)]\nfor i in range(n):\n    x = list(map(int,input().split()))\n    for j in range(2,x[1]+2):\n        mp[x[0]-1].append(x[j]-1)\n    mp[x[0]-1].sort()\nfor i in range(n):\n    if rp[i][0] == 0:\n        p += 1\n        saiki(i)\nfor i in range(n):\n    print(i+1,rp[i][0],rp[i][1])\n\n", "\nn=int(input())\nused=[False for i in range(n)]\nd=[0 for i in range(n)]\nf=[0 for i in range(n)]\nmat=[]\nfor i in range(n):\n    tmp=list(map(int,input().split()))\n    mat.append(tmp[2:])\n\nt=1\ndef dfs(now):\n    global t\n    if used[now]:\n        return\n    else:\n        used[now]=True\n    d[now]=t\n    t+=1\n    for i in range(len(mat[now])):\n        dfs(mat[now][i]-1)\n    f[now]=t\n    t+=1\n\nfor i in range(n):\n    if used[i]==False:\n        dfs(i)\nfor i in range(n):\n    print(i+1,d[i],f[i])\n\n", "n = int(input())\ng = [[]for i in range(n)]\nfor i in range(n):\n    v = list(map(int,input().split()))\n    u = v[0]-1\n    k = v[1]\n    for j in range(k):\n        g[u].append(v[j+2]-1)\ntime = 1\nans = []\nd = [0]*n\nf = [0] *n\nvisited = [0]*n\n\ndef dfs(now,last = -1):\n    global time\n    \n    visited[now] = 1\n    d[now] = time\n    time += 1\n    for next in g[now]:\n        if visited[next]:continue\n        dfs(next,now)\n    f[now] = time\n    time +=1\n    \nfor i in range(n):\n    if not visited[i]:dfs(i)\nfor i in range(n):\n    print(i+1,d[i],f[i])\n    \n    \n        \n        \n", "n = int(input())\ng = [[]] * n\nfor i in range(n) :\n    dat = list(map(int, input().split()))\n    src = dat.pop(0) - 1\n    g[src] = dat[1:]\n    g[src].sort()\n    for j in range(dat[0]) :\n        g[src][j] -= 1\n\nd = [-1] * n\nf = [-1] * n\ndef dfs (v, time) :\n    d[v] = time\n    time += 1\n    for u in g[v] :\n        if d[u] == -1 :\n            time = dfs(u, time)\n    f[v] = time\n    return time + 1\n\nt = 1\nfor v in range (n) :\n    if d[v] == -1 :\n        t = dfs(v, t)\n\nfor v in range (n) :\n    print(v + 1, d[v], f[v])\n", "import sys\nimport math\nimport string\nimport fractions\nimport random\nfrom operator import itemgetter\nimport itertools\nfrom collections import deque\nimport copy\nimport heapq\nimport bisect\n\nMOD = 10 ** 9 + 7\nINF = float('inf')\ninput = lambda: sys.stdin.readline().strip()\n\nsys.setrecursionlimit(10 ** 8)\n\nn = int(input())\ninfo = [list(map(int, input().split())) for _ in range(n)]\nans = [[i + 1, -1, -1] for i in range(n)]\ncheck = [0 for _ in range(n)]\ntime = 1\n\n\ndef dfs(num):\n    check[num] = 1\n    global time\n    if ans[num][1] == -1:\n        ans[num][1] = time\n        time += 1\n    for i in info[num][2:]:\n        if check[i - 1] == 0:\n            dfs(i - 1)\n    if ans[num][2] == -1:\n        ans[num][2] = time\n        time += 1\n\n\nfor i in range(n):\n    if check[i] == 0:\n        dfs(i)\n\nfor i in ans:\n    i = list(map(str, i))\n    print(\" \".join(i))\n\n", "import sys\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\n\nN = int(readline())\nG = [None]*(N+1)\nfor i in range(N):\n    u, k, *vs = map(int, readline().split())\n    G[u] = vs\n\n\nbegin = [-1]*(N+1)\nend = [-1]*(N+1)\nlb = iter(range(1, 2*N+1)).__next__\ndef dfs(v):\n    begin[v] = lb()\n    for w in G[v]:\n        if begin[w] != -1:\n            continue\n        dfs(w)\n    end[v] = lb()\n\n\nfor v in range(1, N+1):\n    if begin[v] != -1:\n        continue\n    dfs(v)\nwrite(\"\\n\".join(\"{} {} {}\".format(*args) for args in zip(range(1, N+1), begin[1:], end[1:])))\nwrite(\"\\n\")\n\n\n", "n = int(input())\npath = []\nfor _ in range(n):\n    l = [int(i) - 1 for i in input().split()[2:]]\n    path.append(l)\n\nstart, end = [0] * n, [0] * n\ncnt = 1\n\ndef rec(x):\n    global cnt\n    start[x] = cnt\n    cnt += 1\n    \n    for y in path[x]:\n        if start[y] > 0: continue\n        rec(y)\n    end[x] = cnt\n    cnt += 1\n\nfor i in range(n):\n    if start[i] > 0: continue\n    rec(i)\n\nfor i in range(n):\n    print(i+1, start[i], end[i])\n\n", "# -*- coding: utf-8 -*-\n\nimport sys\nsys.setrecursionlimit(10 ** 9)\ndef input(): return sys.stdin.readline().strip()\ndef INT(): return int(input())\ndef MAP(): return map(int, input().split())\ndef LIST(): return list(map(int, input().split()))\nINF=float('inf')\n\nN=INT()\nnodes=[[] for i in range(N)]\nfor i in range(N):\n    l=LIST()\n    u=l[0]\n    l=l[2:]\n    for v in l:\n        nodes[u-1].append(v-1)\n    nodes[u-1].sort()\n\nans=[[0]*2 for i in range(N)]\nvisited=[False]*N\ntime=0\ndef rec(u):\n    if visited[u]:\n        return\n    visited[u]=True\n    global time\n    time+=1\n    ans[u][0]=time\n    for v in nodes[u]:\n        rec(v)\n    time+=1\n    ans[u][1]=time\n\nfor i in range(N):\n    rec(i)\nfor i in range(N):\n    d,f=ans[i]\n    print(i+1, d, f)\n\n", "def DFS(num):\n    global time\n    time +=1\n    color[num]=\"gray\"\n    D[num][0]=time\n    for i in M[num]:\n        if color[i]==\"white\":\n            DFS(i)\n    color[num]=\"black\"\n    time +=1\n    D[num][1]=time\n\n\nn=int(input())\nM=[[] for _ in range(n+1)]\nfor i in range(n):\n    for j in list(map(int,input().split()))[2:]:\n        M[i+1].append(j)\ncolor=[\"white\" for _ in range(n+1)]\nD=[[0,0] for _ in range(n+1)]\ntime=0\nfor i in range(n):\n    if color[i+1]==\"white\":\n        DFS(i+1)\n\nfor i in range(n):\n    print(i+1,*D[i+1])\n", "N = int(input())\nedge = [[0] for _ in range(N)]\nfor i in range(N):\n    A = list(map(int, input().split()))\n    for i,a in enumerate(A):\n        A[i] -= 1\n    edge[A[0]] = sorted(A[2:])\nans = [[0,0] for _ in range(N)]\nimport sys\nsys.setrecursionlimit(10**8)\n\ndef dfs(v,now):\n    if len(edge[v])>0:\n        for u in edge[v]:\n            if visited[u]==False:\n                visited[u]=True\n                now += 1\n                ans[u][0] = now\n                now = dfs(u,now)\n    now += 1\n    ans[v][1] = now\n    return now\n\nvisited = [False]*N\n\nnow = 0\nfor i in range(N):\n    if visited[i]==False:\n        visited[i]=True\n        now += 1\n        ans[i][0] = now\n        now = dfs(i,now)\nfor i in range(N):\n    ans[i] = '{} {} {}'.format(i+1,ans[i][0],ans[i][1])\nprint(*ans,sep='\\n')\n", "j = 1\n\ndef dfs(graph, start, result, visited=None):\n    global j\n    if visited == None:\n        visited = []\n    visited.append(start)\n    result[start][1]  = j\n    for next in graph[start][2:]:\n        if next in visited:\n            continue\n        j += 1\n        dfs(graph, next, result, visited)\n    else:\n        j += 1\n        result[start][2] = j\n\nn = int(input())\ng = [[]]\nr = [[i,0,0] for i in range(n + 1)]\nv = []\n\nfor i in range(n):\n    g.append(list(map(int, input().split())))\n\n\nfor i in range(1, n + 1):\n    if i in v:\n        continue\n    dfs(g,i,r,v)\n    j += 1\n\nfor i in range(1,n+1):\n    print(*r[i])\n", "import sys\nsys.setrecursionlimit(1000000)\n\nN=int(input())\nG=[list(map(int, input().split()))[2:] for _ in range(N)]\n\nv=[False]*N\nd=[0]*N\nf=[0]*N\ntimecount=1\n\ndef dfs(i):\n    global timecount\n    if v[i] : return\n    v[i] = True\n    d[i] = timecount\n    # print(\"D\",i+1,timecount)\n    timecount += 1\n    for p in G[i]:\n        dfs(p-1)\n    # print(\"F\",i+1,timecount)\n    f[i] = timecount\n    timecount += 1\n    return\n\nfor i in range(N):\n  if v[i]==0: dfs(i)\n\nfor i in range(N):\n    print(i+1, d[i], f[i])\n", "from collections import defaultdict\n\n\nclass Graph:\n    \"\"\"Graph\n    Directed Unweighted Graph\n    \"\"\"\n\n    def __init__(self):\n        self.graph = defaultdict(list)\n        self._time = 1\n\n    def add(self, vertex: int, neighbors: list):\n        if len(neighbors) == 1:\n            self.graph[vertex - 1] = []\n\n        for nv in neighbors[1:]:\n            self.graph[vertex - 1].append(nv - 1)\n\n    def init(self):\n        r = range(len(self.graph))\n        self.visits = [False for _ in r]\n        self.ins = [0 for _ in r]\n        self.outs = [0 for _ in r]\n        self._time = 1\n\n    def dfs(self, start: int):\n        self.visits[start] = True\n        self.ins[start] = self._time\n        self._time += 1\n\n        for nv in self.graph[start]:\n            if self.is_visited(nv):\n                continue\n\n            self.visits[nv] = True\n            self.dfs(nv)\n\n        self.outs[start] = self._time\n        self._time += 1\n\n    def is_visited(self, vertex: int):\n        return self.visits[vertex]\n\n    def __str__(self) -> str:\n        res = []\n        for i in range(len(self.graph)):\n            res.append(f\"{i + 1} {self.ins[i]} {self.outs[i]}\")\n        return \"\\n\".join(res)\n\n\ndef main():\n    n = int(input())\n    r = range(n)\n\n    graph = Graph()\n\n    for _ in r:\n        line = list(map(int, input().split()))\n        vertex = line[0]\n        graph.add(vertex, line[1:])\n\n    graph.init()\n\n    for start in r:\n        if not graph.is_visited(start):\n            graph.dfs(start)\n\n    print(graph)\n\n\nif __name__ == \"__main__\":\n    main()\n\n", "n = int(input())\ndata = []\n\n# \u6728\u306e\u69cb\u7bc9\u30d5\u30a7\u30fc\u30ba\ntree = [[] for _ in range(n + 1)]\nf = [None] * (n + 1)\nv = [None] * (n + 1)\n\nfor _ in range(n):\n    line = list(map(int, input().strip().split()))\n    node_id = line[0]\n    num_edges = line[1]\n    if num_edges > 0:\n        children = line[2:]\n    else:\n        children = []\n\n    tree[node_id] = children\n\n\n# \u6728\u306e\u63a2\u7d22\u30d5\u30a7\u30fc\u30ba\ntime = 0\ndef dfs(node_id):\n    global time\n    if v[node_id] is not None:\n        # \u8a2a\u554f\u6e08\u307f\n        return\n\n    time += 1\n    v[node_id] = time\n    children = sorted(tree[node_id])\n\n    for child_id in children:\n        dfs(child_id)\n\n    time += 1\n    f[node_id] = time\n\n\ndfs(1)\nwhile any([_v is None for _v in v[1:]]):\n    node_ids = [i for i in range(1, n + 1) if v[i] is None]\n    node_id = node_ids[0]\n    dfs(node_id)\n\n\nfor node_id in range(1, n + 1):\n    print(node_id, v[node_id], f[node_id])\n\n", "import sys\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\n\nn = int(input())\nG = [None for i in range(n+1)]\nfor i in range(n):\n    node_id, k, *adj = map(int, readline().split())\n    # adj.sort()\n    G[node_id] = adj\n\nbegin = [0,]*(n+1)\nend = [0,]*(n+1)\ntime = 1\n\ndef dfs(v):\n    global time\n\n    begin[v] = time\n\n    adjlen = len(G[v])\n    for i in range(adjlen):\n        if begin[G[v][i]] != 0:\n            continue\n        time += 1\n        dfs(G[v][i])\n    time += 1\n    end[v] = time\n\nfor i in range(1, n+1):\n    if begin[i] == 0:\n        if i != 1:\n            time += 1 #\u65b0\u3057\u304f\u59cb\u70b9\u3092\u9078\u3076\u306e\u306b\u3082\u30b3\u30b9\u30c8\u304c\u304b\u304b\u308b\n        dfs(i)\n\nfor i in range(1, n+1):\n    write(str(i) + \" \" + str(begin[i]) + \" \" + str(end[i]) + \"\\n\")\n", "n = int(input())\ng, d, f = [], [], []\nfor _ in range(n):\n    g.append([])\n    d.append(0)\n    f.append(0)\nfor _ in range(n):\n    vs = list(map(lambda x: int(x) - 1, input().split()))\n    g[vs[0]] = vs[2:]\n\n\ndef dfs(v, t):\n    if d[v] > 0:\n        return t\n    d[v] = t\n    t += 1\n    while len(g[v]) > 0:\n        visitting = g[v].pop(0)\n        t = dfs(visitting, t)\n    f[v] = t\n    return t + 1\n\n\nt = 1\nfor v in range(n):\n    t = dfs(v, t)\n    print(v + 1, d[v], f[v])\n\n", "import sys\n\ndef debug(x, table):\n    for name, val in table.items():\n        if x is val:\n            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)\n            return None\n\ntime = 0\n\ndef dfs(u, adj, d, f, sumi):\n    global time\n    sumi.add(u)\n    time += 1\n    d[u] = time\n\n    for v in adj[u]:\n        if v not in sumi:\n            dfs(v, adj, d, f, sumi)\n            \n    time += 1\n\n    f[u] = time\n\n\ndef solve():\n    n = int(input())\n    adj = [None] * n\n\n    for i in range(n):\n        u, k, *vs = [int(j) - 1 for j in input().split()]\n        # debug(vs, locals())\n        adj[u] = vs\n\n    # debug(adj, locals())\n    \n    d = [0] * n\n    f = [0] * n\n    sumi = {0}\n    mitan = set(range(1, n))\n\n    dfs(0, adj, d, f, sumi)\n    mitan -= sumi\n    # debug(mitan, locals())\n\n    \n    while mitan:\n        u = min(mitan)\n        dfs(u, adj, d, f, sumi)\n        mitan -= sumi\n        # debug(mitan, locals())\n        \n\n    for i in range(n):\n        print(i + 1, d[i], f[i])\n\n    pass\n\nif __name__ == '__main__':\n    solve()\n", "def setD(x):\n  global TM\n  DL[x] = TM\n  TM += 1\n  delPoint(x)\ndef setC(x):\n  global TM\n  CL[x] = TM\n  TM += 1\n\ndef delPoint(x):\n  for i in range(N):\n    for j in range(len(PL[i])-1, -1, -1):\n      if PL[i][j]==x: del PL[i][j]\n\nN = int(input())\nPL, DL, CL, ST = [[] for _ in range(N)], [None]*N, [None]*N, []\nfor i in range(N):\n  tl = list(map(int, input().split()))\n  for j in range(tl[1]): PL[i].append(tl[2+j]-1)\nTM = 1\nwhile True:\n  tl = list(filter(lambda x: len(x[1])>0, enumerate(PL)))\n  if len(tl)==0: break\n  ST.append(min(tl)[0])\n  while len(ST)>0:\n    if DL[ST[-1]]==None:\n      #print(PL, DL, CL, ST, TM, \"A\")\n      setD(ST[-1])\n      if len(PL[ST[-1]])>0: ST.append(PL[ST[-1]][0])\n    else:\n      #print(PL, DL, CL, ST, TM, \"B\")\n      tp = ST[-1]\n      if len(PL[tp])==0:\n        ST.pop()\n        if CL[tp]==None:\n          setC(tp)\n      else:\n        ST.append(PL[tp][0])\nfor i in range(N):\n  print(\"{} {} {}\".format(i+1, DL[i], CL[i]))\n\n", "def dfs(graph_dict, node_num):\n\n    isvisited = [False] * node_num\n    t_d = [0] * node_num\n    t_f = [0] * node_num\n    t = 1\n    rootlist = []\n    ind = 1\n\n    t_d[0] = t\n    t += 1\n    isvisited[0] = True\n\n    while True:\n        for i in graph_dict[ind]:\n            if not isvisited[i-1]:\n                rootlist.append(ind)\n                ind = i\n                t_d[ind-1] = t\n                t += 1\n                isvisited[ind-1] = True\n                break\n        else:\n            t_f[ind-1] = t\n            t += 1\n            try:\n                ind = rootlist.pop()\n            except:\n                for i in range(node_num):\n                    if not isvisited[i]:\n                        isvisited[i] = True\n                        t_d[i] = t\n                        t += 1\n                        ind = i + 1\n                        break\n                else:\n                    return t_d, t_f\n\n\ndef main():\n\n    n = int(input())\n    gd = {}\n    for _ in range(n):\n        i, _,  *l = map(int, input().split())\n        gd[i] = l\n    td, tf = dfs(gd, n)\n    for i, tdi, tfi in zip(range(n), td, tf):\n        print(i+1, tdi, tfi)\n\nmain()\n\n\n", "p = 0\n# \u6df1\u3055\u512a\u5148\u63a2\u7d22\ndef depth_first_search(g, s, v, f, l):\n    global p\n    p += 1\n    f[v] = p\n    s[v] = True  # v \u3092\u8a2a\u554f\u6e08\u307f\u3068\u3059\u308b\n    for nv in g[v]:\n        if s[nv]: continue  # \u65e2\u306b\u8a2a\u554f\u6e08\u307f\u306e\u9802\u70b9\u306f\u63a2\u7d22\u3057\u306a\u3044\n        depth_first_search(g, s, nv, f, l)  # \u518d\u5e30\u7684\u306b\u63a2\u7d22\n    p += 1\n    l[v] = p\n\n    return\n\n\nn = int(input())\n\n# \u30b0\u30e9\u30d5\u5165\u529b\u53d7\u3051\u53d6\u308a (\u3053\u3053\u3067\u306f\u7121\u5411\u30b0\u30e9\u30d5\u3092\u60f3\u5b9a)\ngraph = [[] for _ in range(n)]\nfor i in range(n):\n    l = list(map(int, input().split()))\n    for j in range(l[1]):\n        if (l[0] - 1) == l[2 + j] - 1:\n            continue\n        graph[l[0] - 1].append(l[2 + j] - 1)\n\nseen = [False] * n  # \u5168\u9802\u70b9\u3092 False(\u672a\u8a2a\u554f) \u306b\u521d\u671f\u5316\nfirst_order = [-1] * n\nlast_order = [-1] * n\n\nfor i in range(n):\n    if seen[i] == False:\n        depth_first_search(graph, seen, i, first_order, last_order)  # \u9802\u70b9 0 \u3092\u30b9\u30bf\u30fc\u30c8\u3068\u3057\u305f\u63a2\u7d22\n\nfor i in range(n):\n    print(i + 1, first_order[i], last_order[i])\n\n", "# \u6df1\u3055\u512a\u5148\u63a2\u7d22\uff08\u884c\u304d\u304c\u3051\u3001\u5e30\u308a\u304c\u3051\uff09\nimport sys\ninput = sys.stdin.readline\nfrom collections import deque\n\n# \u30b0\u30e9\u30d5\u306e\u4f5c\u6210(\u7121\u5411\u30b0\u30e9\u30d5\u3067\u306f#\u3092\u6d88\u3059)\nN = int(input())\ngraph = [deque([]) for _ in range(N + 1)]\nfor _ in range(N):\n    u, k, * v = [int(x) for x in input().split()] # u\u306f\u9802\u70b9\u756a\u53f7\u3001k\u306f\u96a3\u63a5\u9802\u70b9\u306e\u500b\u6570\n    v.sort()\n    for i in v:\n        graph[u].append(i)\n        # graph[i].append(u) # \u7121\u5411\u30b0\u30e9\u30d5\n\ntime = 0\narrive_time = [-1] * (N + 1) # \u5230\u7740\u6642\u523b\nfinish_time = [-1] * (N + 1) # \u63a2\u7d22\u7d42\u4e86\u6642\u523b\n\n# \u6df1\u3055\u512a\u5148\u63a2\u7d22\ndef dfs(v):\n    global time\n    time += 1\n    stack = [v]\n    arrive_time[v] = time\n    while stack:\n        v = stack[-1]\n        if graph[v]:\n            w = graph[v].popleft()\n            if arrive_time[w] < 0:\n                time += 1\n                arrive_time[w] = time\n                stack.append(w) \n        else:\n            time += 1\n            finish_time[v] = time\n            stack.pop()          \n    return [arrive_time, finish_time]\n\n# \u5b64\u7acb\u3057\u3066\u3044\u308b\u9802\u70b9\u5bfe\u7b56\nfor i in range(N):\n    if arrive_time[i + 1] < 0:\n        ans = dfs(i + 1)\n\n# \u9802\u70b9\u756a\u53f7\u3001\u5230\u7740\u6642\u523b\u3001\u7d42\u4e86\u6642\u523b\nfor j in range(N):\n    temp = [j + 1, ans[0][j + 1], ans[1][j + 1]]\n    print(* temp)\n", "lst = []\nn = int(input())\ndlst = [0]*n\nflst = [0]*n\ncolorlst = [0]*n\ntime = 0\n\nfor i in range(n):\n    tmplst = [0]*n\n    lst.append(tmplst)\n\nfor i in range(n):\n    uklst = list(map(int, input().split()))\n    s = uklst[1]\n    num = uklst[0]\n    for j in range(s):\n        lst[num-1][uklst[j+2]-1] = 1\n\n\ndef dfs(u):\n    global time\n    time += 1\n    colorlst[u-1] = 1\n    dlst[u-1] = time\n\n    for i in range(1, n+1):\n        if lst[u-1][i-1] and colorlst[i-1] == 0:\n            dfs(i)\n\n    colorlst[u-1] = 2\n    time += 1\n    flst[u-1] = time\n\nwhile 0 in dlst:\n    for i in range(n):\n        if dlst[i] == 0:\n            dfs(i+1)\n\n\n\nfor i in range(n):\n    print(i+1, dlst[i], flst[i])\n", "def dfs(G,n):\n\n\tglobal ptr\n\t\n\t#\u63a2\u7d22\u6e08\n\tseen[n] = True\n\n\t#\u884c\u304d\n\tF[n] = ptr\n\tptr += 1\n\n\tfor i in G[n]:\n\t\t#\u6b21\u306b\u884c\u3051\u308b\u304b\u3092\u5224\u5b9a\n\t\tif seen[i] == True :\n\t\t\tcontinue\n\t\tdfs(G,i)\n\n\t#\u5e30\u308a\n\tL[n] = ptr\n\tptr += 1\n\nif __name__ == '__main__':\n\n\tn = int(input())\n\t\n\tG = [[] for _ in range(n+1)] \n\tF = [0 for _ in range(n+1)]\n\tL = [0 for _ in range(n+1)]\n\n\t#\u6df1\u3055\u512a\u5148\u63a2\u7d22\n\t#\u63a2\u7d22\u6e08\u914d\u5217\n\tseen = [False for _ in range(n+1)]\n\n\tfor i in range(n):\n\t\tcmd = list(map(int,input().split()))\n\t\tm = cmd[1]\n\t\tif m != 0:\n\t\t\tfor j in range(m):\n\t\t\t\tG[i+1].append(cmd[j+2])\n\tptr = 1\n\tfor i in range(1,n):\n\t\tif seen[i] == False :\n\t\t\tdfs(G,i)\n\n\tfor i in range(1,n+1):\n\t\tprint(i,F[i],L[i])\n\n\n", "n=int(input())\nG=[[j for j in range(n)] for i in range(n)]\nfor i in range(n):\n    g_in=list(map(int,input().split()))\n    u=g_in[0]\n    k=g_in[1]\n    v=g_in[2:]\n    for j in v:\n        G[u-1][j-1]=1\n\nvisited=[0 for i in range(n)]\nfinished=[0 for i in range(n)]\nL=[]\nout=[[i+1,0,0] for i in range(n)]\nstep=0\n\ndef dfs(cn):\n    flg=0\n    if visited[cn]==0:\n        flg=1\n        L.append(cn)\n    visited[cn]=1\n    for i in range(n):\n        if cn!=i and G[cn][i]==1 and visited[i]==0:\n            dfs(i)\n    if flg==1:\n        L.append(cn)\n\ni=0\nwhile visited.count(1)<n:\n    dfs(i)\n    i+=1\ncopied=[0 for i in range(len(L))]\n\nfor i in range(len(L)):\n    if copied[L[i]]==0:\n        copied[L[i]]=1\n        out[L[i]][1]=i+1\n    elif copied[L[i]]==1:\n        copied[L[i]]=2\n        out[L[i]][2]=i+1\n\nout=[' '.join(map(str,i)) for i in out]\n#print(' '.join(map(str,[i+1 for i in L])))\nprint('\\n'.join(map(str,out)))\n", "import sys\nsys.setrecursionlimit(10000000)\nMOD = 10 ** 9 + 7\nINF = 10 ** 15\n\nG = [[] for _ in range(105)]\nbegin = [-1] * 105\nend = [-1] * 105\n\nt = 1\ndef dfs(v):\n    global t\n    begin[v] = t\n    t += 1\n    for e in G[v]:\n        if begin[e] < 0:\n            dfs(e)\n    end[v] = t\n    t += 1\n\ndef main():\n    N = int(input())\n    for i in range(N):\n        A = list(map(int,input().split()))\n        for a in A[2:]:\n            G[i].append(a - 1)\n    \n    for i in range(N):\n        if begin[i] < 0:\n            dfs(i)\n    for i in range(N):\n        print(i + 1,begin[i],end[i])\nif __name__ == '__main__':\n    main()\n", "# -*- coding: utf-8 -*-\nimport sys\nsys.setrecursionlimit(100000)\nN = int(input())\nadj = [[0]*N for _ in range(N)]\nsearched = {n: 0 for n in range(N)}\nedge = {}\n\nfor n in range(N):\n    inp = list(map(int, input().split()))\n    edge[n] = inp[1]\n    for i in inp[2:]:\n        adj[inp[0]-1][i-1] = 1\n\ntime = 1\nstack = []\nunsearch = set(range(N))\nuncomplete = set(range(N))\nresult = {n:{\"found\": 0, \"finish\": 0} for n in range(N)}\n\ndef DFS(i):\n    global time\n    global unsearch\n    \n    itr = sorted(unsearch)\n    \n    for j in itr:\n        if adj[i][j] == 1 and j in unsearch:\n            result[j][\"found\"] = time\n            time += 1\n            unsearch.remove(j)\n            DFS(j)\n    result[i][\"finish\"] = time\n    time += 1\n    \nwhile len(unsearch):\n    i = min(unsearch)\n    unsearch.remove(i)\n    result[i][\"found\"] = time\n    time += 1\n    DFS(i)\n\nfor n in range(N):\n    print(\"{} {} {}\".format(n+1, result[n][\"found\"], result[n][\"finish\"])) \n", "def dfs(v,time):\n    d[v]=time\n    for v2 in G[v]:\n        if d[v2]!=-1:\n            continue\n        time=dfs(v2,time+1)\n    time+=1\n    f[v]=time\n    return time\n\n\n\nN=int(input())\nG={}\nfor i in range(N):\n    line=list(map(int,input().split()))\n    G[line[0]]=line[2:]\n\nd=[-1]*(N+1)\nf=[-1]*(N+1)\ntime=1\nfor i in range(1,N+1):\n    if d[i]==-1:\n        time=dfs(i,time)+1\n\nfor i in range(1,N+1):\n    print(i,d[i],f[i])\n\n\n\n\n", "class Node:\n  def __init__(self, name):\n    self.name = name\n    self.start = 0\n    self.end = 0\n    self.child = []\n    self.visited = False\n\n  def dfs(self, s, nodes):\n    if self.visited:\n      return s\n\n    self.visited = True\n    self.start = s\n    next_start = self.start + 1\n    for i in self.child:\n      if self.name == i:\n        continue\n\n      next_start = nodes[i-1].dfs(next_start, nodes)\n    self.end = next_start\n    return self.end + 1\n\ndef main():\n  n = int(input())\n  nodes = []\n  for _ in range(n):\n    u, k, *v = map(int, input().split())\n    node = Node(u)\n    node.child = v\n    nodes.append(node)\n\n  next_start = 1\n  for node in nodes:\n    if node.visited:\n      continue\n    next_start = node.dfs(next_start, nodes)\n\n  for node in nodes:\n    print(f'{node.name} {node.start} {node.end}')\n\nmain()\n\n", "import re\nimport sys\nimport math\nimport itertools\nimport bisect\nimport heapq#.heapify:Priority Queue\u306b\u5909\u63db \n#.heappop:\u6700\u5c0f\u5024\u53d6\u5f97, .heappush:\u8981\u7d20\u633f\u5165\nfrom copy import copy,deepcopy\nfrom collections import deque,Counter,defaultdict\nfrom decimal import Decimal\nimport functools\nfrom functools import reduce\ndef v(): return input()\ndef k(): return int(input())\ndef S(): return input().split()\ndef I(): return map(int,input().split())\ndef X(): return list(input())\ndef L(): return list(input().split())\ndef l(): return list(map(int,input().split()))\ndef Z(): return tuple(map(int,input().split()))\ndef lcm(a,b): return a*b//math.gcd(a,b)\ndef gcd(*numbers):\n    return reduce(math.gcd, numbers)\nsys.setrecursionlimit(10 ** 6)\nmod = 10**9+7\nINF = float(\"inf\")\ncnt = 0\nans = 0\n\ndef dfs(G,v):\n    global d,f,t\n    d[v-1] = t\n    t += 1\n    for node in G[v-1]:\n        if d[node-1]<0 and node>0:\n            dfs(G,node)\n    f[v-1] = t\n    t += 1\n\n\nn = k()\nG = [l()[2:] for _ in range(n)]\nd,f = [-1]*n,[-1]*n\nt = 1\nfor i in range(1,n):\n    if d[i-1] < 0:\n        dfs(G,i)\n\nfor i in range(n):\n    print(f\"{i+1} {d[i]} {f[i]}\")\n", "N=int(input())\nm=[[0 for i in range(N)]  for j in range(N)]\nfor i in range(N):\n u,k,*array=map(int,input().split())\n for v in array:\n  m[u-1][v-1]=1\ntime=1\nD=[-1 for m in range(N)]\nF=[-1 for n in range(N)]\ndef dfs(src):\n global time\n D[src]=time\n time+=1\n for dst in range(N):\n  if m[src][dst]==1 and D[dst]<0:\n   dfs(dst)\n F[src]=time\n time+=1\nfor root in range(N):\n if D[root]<0:\n  dfs(root)\nfor result in range(N):\n print(result+1,D[result],F[result])\n", "import sys\nimport os\n\n\nfn = \"inputdata.txt\"\nif os.path.exists(fn):\n    sys.stdin = open(fn)\n    \nn= int(sys.stdin.readline())\n\nclass Node:\n    def __init__(self,M):\n        self.time=0\n        self.complete=0\n        self.nexts=M[2:]\n        \nclass Graph():\n    def __init__(self,n,Ms):  \n        self.nodes=[Node(M) for M in Ms]\n        self.tm=0\n        self.visited=[False]*n\n    def findnode(self,t):\n        self.tm+=1\n        self.nodes[t].time=self.tm\n        self.visited[t]=True\n        for  np in self.nodes[t].nexts:\n            if self.visited[np-1]:\n                continue\n            self.findnode(np-1)\n        self.tm+=1\n        self.nodes[t].complete=self.tm\n    def print(self):\n        for i,p in enumerate(self.nodes):\n            print(*(i+1,p.time,p.complete))     \n    \n        \nM=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]\ngraph=Graph(n,M)\ns=0\nwhile 1:\n    graph.findnode(s) \n    if not False in graph.visited:\n        break\n    s=graph.visited.index(False)\ngraph.print()\n", "def dfs(adjlist,v):\n    global d,f,t\n    d[v-1]=t\n    t+=1\n    for node in adjlist[v-1]:\n        if d[node-1]<0 and node>0:\n            dfs(adjlist,node)\n    f[v-1]=t\n    t+=1\n\nn=int(input())\nadjlist=[list(map(int,input().split()))[2:] for _ in range(n)]\nd=[-1]*n\nf=[-1]*n\nt=1\nfor i in range(1,n):\n    if d[i-1]<0:\n       dfs(adjlist,i)\nfor i in range(n):\n    print(\"{} {} {}\".format(i+1,d[i],f[i]))\n", "import sys\nif sys.platform =='ios':\n\timport clipboard\n\ta=clipboard.get()\n\ta = a.split('\\n')\n\ttext = '\\n'.join(a)\n\twith open('input_file.txt','w') as f:\n\t\tf.write(text)\n\tsys.stdin = open('input_file.txt')\nsys.setrecursionlimit(410000000)\nstdin = sys.stdin \nni = lambda: int(ns())\nna = lambda: list(map(int, stdin.readline().split()))\nns = lambda: stdin.readline().strip()\nnm = lambda: map(int,input().split())\nna_1 = lambda: list(map(lambda x:int(x)*(-1), stdin.readline().split()))\nna_2 = lambda: list(map(lambda x:int(x)-1, stdin.readline().split()))\nfrom collections import defaultdict\n\nn = ni()\nG = [[]for i in range(n)]\nfor i in range(n):\n\tu,k,*v = nm()\n\tfor j in range(k):\n\t\tG[u-1].append(v[j]-1)\n\t\t\ndef dfs(x):\n\tglobal t\n\tS[x] = t\n\tseen.add(x)\n\tfor nv in G[x]:\n\t\tif nv in seen:\n\t\t\tcontinue\n\t\tt += 1\n\t\tdfs(nv)\n\tt += 1\n\tF[x] = t\n\t\nS = [0]*n\nF = [0]*n\n\nseen = set()\n\nt = 1\nfor i in range(n):\n\tif i not in seen:\n\t\tdfs(i)\n\t\tt += 1\n\t\t\nfor i in range(n):\n\tprint(i+1,S[i],F[i])\t\n\t\n", "n = int(input())\n\nnode_ls = []\nchild = {}\nvisited = {}\n\nd = {}\nf = {}\nstep = 0\n\n\ndef dfs(node):\n    \n    if visited[node]:\n        return\n    \n    visited[node] = True\n    \n    global step\n    step += 1\n    d[node] = step\n    \n    for no in child[node]:\n        dfs(no)\n    \n    step += 1\n    f[node] = step\n    \n    return \n    \n    \ndef main():\n    for _ in range(n):\n        node, num, *t = list(map(int, input().split()))\n        \n        node_ls.append(node)\n        visited[node] = False\n\n        if num != 0:\n            child[node] = t    \n        elif num == 0:\n            child[node] = []    \n        \n    for node in node_ls:\n        dfs(node)\n    \n    \n    for i in node_ls:\n        print(i, d[i], f[i])\n    \n    \nif __name__ == '__main__':\n    main()\n", "n = int(input())\na = [[] for i in range(n)]\n\nfor i in range(n):\n    v = list(map(int, input().split()))\n    u = v[0] - 1\n    for j in v[2:]:\n        a[u].append(j-1)\n\nd = [0] * n\nf = [0] * n\nisDiscovered = [False] * n\ntime_stamp = 0\n\ndef dfs(x):\n    global time_stamp\n    isDiscovered [x] = True\n    time_stamp += 1\n    d[x] = time_stamp\n    for i in a[x]:\n        if not isDiscovered[i]:\n            dfs(i)\n    time_stamp += 1\n    f[x] = time_stamp\n\nfor i in range(n):\n    if not isDiscovered[i]:\n        dfs(i)\n\nfor i in range(n):\n    print(i+1, d[i], f[i])\n", "# DFS(\u518d\u5e30\uff09 v:\u9802\u70b9\ndef DFS(v,dis,fin):\n  global time\n  # \u8a2a\u554f\u3057\u305f\u306e\u3067\u767a\u898b\u6642\u523b\u3092\u8a18\u5165\n  dis[v] = time\n  time += 1\n  \n  # v\u306b\u96a3\u63a5\u3057\u3066\u3044\u308b\u9802\u70b9\u3092\u307f\u308b\n  for u in V[v]:\n    if dis[u] is None:\n      DFS(u,dis,fin)\n  \n  # \u51e6\u7406\u304c\u5b8c\u4e86\u3057\u305f\u306e\u3067\u5b8c\u4e86\u6642\u523b\u3092\u8a18\u5165\n  fin[v] = time\n  time += 1\n  \nn = int(input())\n# 0\u756a\u76ee\u3092\u59cb\u70b9\u3068\u3057\u3066\u521d\u671f\u5316\nV = [[i for i in range(n)]]\n\nfor i in range(n):\n  _, __, *a = map(int, input().split())\n  V.append(a)\n\ndis = [None]*(n+1)# \u9802\u70b9\u3092\u767a\u898b\u3057\u305f\u6642\u523b\nfin = [None]*(n+1)# \u9802\u70b9\u306e\u5b8c\u4e86\u6642\u523b\ntime = 0\nDFS(0,dis,fin)\n\nfor i in range(1,n+1):\n  print(i, dis[i], fin[i])\n", "global G, time, visited, d, f\n\nN = int(input())\nG = [[]]\nfor _ in range(N):\n    line = list(map(int,input().split()))\n    G.append(line[2:])\n\nd, f, visited = [0]*(N+1), [0]*(N+1), [0]*(N+1)\ntime = 1\n\ndef dfs(s):\n    global time\n    d[s], visited[s] = time, 1\n    time += 1\n\n    for to in G[s]:\n        if not visited[to]:\n            dfs(to)\n    \n    f[s] = time\n    time += 1\n\nfor i in range(1,N+1):\n    if not visited[i]:\n        dfs(i)\n\nfor i in range(1,N+1):\n    print(\"{0} {1} {2}\".format(i, d[i], f[i]))\n", "n = int(input())\nmat = [[0] * n for _ in range(n)]\nd, f = [0] * n, [0] * n\nfor _ in range(n):\n    adj = list(map(int, input().split()))\n    i = adj[0]\n    v = adj[2:]\n    for j in v:\n        mat[i - 1][j - 1] = 1\n\ntime, current = 0, 0\nstack = []\nwhile 0 in f:\n    if not stack:\n        for i, v in enumerate(f):\n            if v == 0:\n                stack.append(i)\n                time += 1\n                d[i] = time\n                break\n    time += 1\n    current = stack[-1]\n    for i in range(len(mat[current])):\n        if mat[current][i] and not d[i]:\n            current = i\n            d[i] = time\n            stack.append(i)\n            break\n    else:\n        f[current] = time\n        current = stack.pop()\n\nfor l in zip(range(1, n + 1), d, f):\n    print(*l)\n", "n = int(input())\nv_infos = dict()\nfor _ in range(n):\n\tid, v_num, *vs = map(int, input().split())\n\tv_infos[id] = vs\n\nseen_set = set()\nans_list = [None] * (n+1)\ncurrent_time = 0\ndef dfs(id):\n\tglobal current_time\n\tcurrent_time += 1\n\tstart_time = current_time\n\tseen_set.add(id)\n\tnext_v_list = v_infos[id]\n\tfor next_v_id in next_v_list:\n\t\tif next_v_id in seen_set: continue\n\t\tdfs(next_v_id)\n\n\tcurrent_time += 1\n\tend_time = current_time\n\tans_list[id] = [id, start_time, end_time]\n\nfor i in range(1, n+1):\n\tif not i in seen_set:\n\t\tdfs(i)\n\nfor li in ans_list[1:]:\n\tprint(*li)\n", "class DigraphDFSTree:\n    def __init__(self, n):\n        self.n = n\n        self.digraph = [[] for _ in range(n)]\n        self.dfstree = [[] for _ in range(n)]\n        self.par = [-1] * n\n        self.arrival = [-1] * n\n        self.depature = [-1] * n \n        self.roots = set()\n\n    def add_edge(self, v, nxt_v):\n        self.digraph[v].append(nxt_v)\n\n    def build(self, root=None):\n        k = 0\n        idxs = [0] * self.n\n        if root is not None:\n            self.roots.add(v)\n            self._dfs(v, idxs, k)\n        else:\n            for v in range(self.n):\n                if self.arrival[v] == -1:\n                    self.roots.add(v)\n                    k = self._dfs(v, idxs, k)\n\n    def _dfs(self, root, idxs, k):\n        stack = [root]\n        while stack:\n            v = stack[-1]\n            idx = idxs[v]\n            if self.arrival[v] == -1:\n                self.arrival[v] = k\n                k += 1\n            if idx < len(self.digraph[v]):\n                nxt_v = self.digraph[v][idx]\n                idxs[v] += 1\n                if self.arrival[nxt_v] == -1:\n                    self.dfstree[v].append(nxt_v)\n                    self.par[nxt_v] = v\n                    stack.append(nxt_v)\n            else:\n                self.depature[v] = k\n                k += 1\n                stack.pop()\n        return k\n\n\nn = int(input())\ninfo = [list(map(int, input().split())) for i in range(n)]\n\n\ndfst = DigraphDFSTree(n)\nfor v, k, *nxts in info:\n    v -= 1\n    for nxt_v in nxts:\n        nxt_v -= 1\n        dfst.add_edge(v, nxt_v)\n\ndfst.build()\nfor i, (arr, dep) in enumerate(zip(dfst.arrival, dfst.depature)):\n    print(i + 1, arr + 1, dep + 1)\n", "import sys\nsys.setrecursionlimit(10000000)\ninput = sys.stdin.readline\n\nn = int(input())\nes = [0] * n  # \u96a3\u63a5\u30ea\u30b9\u30c8\n\nfor _ in range(n):\n    tmp = list(map(int, input().split()))\n    es[tmp[0] - 1] = map(lambda x: x - 1, tmp[2:])\n\nres = [[-1, -1] for _ in range(n)]\n\n\ndef dfs(v, a):\n    res[v][0] = a\n    a += 1\n    for i in es[v]:\n        if res[i][0] == -1:\n            a = dfs(i, a)\n    res[v][1] = a\n    return a + 1\n\n\na = dfs(0, 1)\nfor i in range(1, n):\n    if res[i][0] == -1:\n        a = dfs(i, a)\n\nfor i in range(n):\n    print(i + 1, res[i][0], res[i][1])\n\n", "N = int(input())\ntree = [None for _ in range(N+1)]\nfor i in range(1, N+1):\n    _, _, *s = list(map(int, input().split()))\n    tree[i] = s\n# print(tree)\n\nd = [-1]*(N+1)\nf = [-1]*(N+1)\nd[0] = 0\n\n\ndef DFS(i, t):\n    d[i] = t\n    if tree[i]:\n        for s in tree[i]:\n            if d[s] < 0:\n                t += 1\n                t = DFS(s, t)\n    t += 1\n    f[i] = t\n    return t\n\n\nt = 0\nwhile -1 in d:\n    i = d.index(-1)\n    t = DFS(i, t+1)\nfor i in range(1, N+1):\n    print(i, d[i], f[i])\n", "n = int(input()) + 1\na = [0] + [[int(j) for j in input().split()][: 1: -1] for _ in range(n - 1)]\nb = [[] for _ in range(n)]\nc = 0\n\nfor m in range(1, n):\n    if not b[m]:\n        l = [m]\n        c += 1\n        while l:\n            i = l[-1]\n            if not b[i]: b[i].append(c)\n            c += 1\n            while a[i]:\n                j = a[i].pop()\n                if not b[j]:\n                    l.append(j)\n                    break\n            else: b[l.pop()].append(c)\n\nfor i in range(1, n): print(i, *b[i])\n", "n = int(input())\n\ngraph = [[0] * n for _ in range(n)]\nfor i in range(n):\n    a = list(map(int,input().split()))\n    for j in range(a[1]):\n        graph[a[0] - 1][a[j + 2] - 1] = 1\n\nvisit = [False] * n # \u8a2a\u554f\u6e08\u307f\u304b\u3069\u3046\u304b\u306e\u5224\u5b9a\ngo = [0] * n # \u767a\u898b\u6642\u523b\nback = [0] * n # \u5b8c\u4e86\u6642\u523b\ntime = 0 # \u305d\u306e\u6642\u306e\u6642\u523b\n\ndef dfs(i):\n    global time\n    time += 1\n    go[i] = time\n    visit[i] = True\n    for j in range(n):\n        if visit[j] == False and graph[i][j] == 1: # \u672a\u8a2a\u554f\u304b\u3064\u884c\u3051\u308b\u6240\n            dfs(j)\n    time += 1\n    back[i] = time\n\nfor i in range(n):\n    if not visit[i]:\n        dfs(i)\n\nfor i in range(n):\n    print(i + 1, go[i], back[i])\n"]

source: aizu

question:
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

![image](1.png)

  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.

data_split: test


E. Dividing Kingdom

problem_index: E

time_limit: 2 seconds

memory_limit: 256 megabytes

input_spec: The first line contains integer n (9 ≤ n ≤ 105) — the number of cities in Flatland. Next n lines each contain two space-separated integers: xi, yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: ![image](images/cf_260_E/1.png).

note:
The solution for the first sample test is shown below:
![image](images/cf_260_E/2.png)
The solution for the second sample test is shown below:
![image](images/cf_260_E/3.png)
There is no solution for the third sample test.

source: codeforces

raw_problem:
E. Dividing Kingdom

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

A country called Flatland is an infinite two-dimensional plane. Flatland has n cities, each of them is a point on the plane.

Flatland is ruled by king Circle IV. Circle IV has 9 sons. He wants to give each of his sons part of Flatland to rule. For that, he wants to draw four distinct straight lines, such that two of them are parallel to the Ox axis, and two others are parallel to the Oy axis. At that, no straight line can go through any city. Thus, Flatland will be divided into 9 parts, and each son will be given exactly one of these parts. Circle IV thought a little, evaluated his sons' obedience and decided that the i-th son should get the part of Flatland that has exactly ai cities.

Help Circle find such four straight lines that if we divide Flatland into 9 parts by these lines, the resulting parts can be given to the sons so that son number i got the part of Flatland which contains ai cities.

Input

The first line contains integer n (9 ≤ n ≤ 105) — the number of cities in Flatland. Next n lines each contain two space-separated integers: xi, yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: .

Output

If there is no solution, print a single integer -1.

Otherwise, print in the first line two distinct real space-separated numbers: x1, x2 — the abscissas of the straight lines that are parallel to the Oy axis. And in the second line print two distinct real space-separated numbers: y1, y2 — the ordinates of the straight lines, parallel to the Ox. If there are multiple solutions, print any of them.

When the answer is being checked, a city is considered to lie on a straight line, if the distance between the city and the line doesn't exceed 10 - 6. Two straight lines are considered the same if the distance between them doesn't exceed 10 - 6.

Examples

Input

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 1 1 1 1 1 1 1 1

Output

1.5000000000 2.5000000000
1.5000000000 2.5000000000

Input

15
4 4
-1 -3
1 5
3 -4
-4 4
-1 1
3 -3
-4 -5
-3 3
3 2
4 1
-4 2
-2 -5
-3 4
-1 4
2 1 2 1 2 1 3 2 1

Output

-3.5000000000 2.0000000000
3.5000000000 -1.0000000000

Input

10
-2 10
6 0
-16 -6
-4 13
-4 -2
-17 -10
9 15
18 16
-5 2
10 -5
2 1 1 1 1 1 1 1 1

Output

-1

Note

The solution for the first sample test is shown below:

The solution for the second sample test is shown below:

There is no solution for the third sample test.

question:
A country called Flatland is an infinite two-dimensional plane. Flatland has n cities, each of them is a point on the plane.
Flatland is ruled by king Circle IV. Circle IV has 9 sons. He wants to give each of his sons part of Flatland to rule. For that, he wants to draw four distinct straight lines, such that two of them are parallel to the Ox axis, and two others are parallel to the Oy axis. At that, no straight line can go through any city. Thus, Flatland will be divided into 9 parts, and each son will be given exactly one of these parts. Circle IV thought a little, evaluated his sons' obedience and decided that the i-th son should get the part of Flatland that has exactly a_{i} cities.
Help Circle find such four straight lines that if we divide Flatland into 9 parts by these lines, the resulting parts can be given to the sons so that son number i got the part of Flatland which contains a_{i} cities.

Input
The first line contains integer n (9 ≤ n ≤ 10^{5}) — the number of cities in Flatland. Next n lines each contain two space-separated integers: x_{i}, y_{i} ( - 10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: ![image](1.png).

Output
If there is no solution, print a single integer -1.
Otherwise, print in the first line two distinct real space-separated numbers: x_{1}, x_{2} — the abscissas of the straight lines that are parallel to the Oy axis. And in the second line print two distinct real space-separated numbers: y_{1}, y_{2} — the ordinates of the straight lines, parallel to the Ox. If there are multiple solutions, print any of them.
When the answer is being checked, a city is considered to lie on a straight line, if the distance between the city and the line doesn't exceed 10^{ - 6}. Two straight lines are considered the same if the distance between them doesn't exceed 10^{ - 6}.

Examples
Input
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1 1 1 1 1 1 1 1 1

Output
1.5000000000 2.5000000000
1.5000000000 2.5000000000

Input
15
4 4
-1 -3
1 5
3 -4
-4 4
-1 1
3 -3
-4 -5
-3 3
3 2
4 1
-4 2
-2 -5
-3 4
-1 4
2 1 2 1 2 1 3 2 1

Output
-3.5000000000 2.0000000000
3.5000000000 -1.0000000000

Input
10
-2 10
6 0
-16 -6
-4 13
-4 -2
-17 -10
9 15
18 16
-5 2
10 -5
2 1 1 1 1 1 1 1 1

Output
-1

Note
The solution for the first sample test is shown below:
 ![image](2.png) The solution for the second sample test is shown below:
 ![image](3.png) There is no solution for the third sample test.

tags: ['Sorting', 'Data structures', 'Complete search']

raw_tags: ['data structures', 'brute force', 'binary search']

image_tags: Math Map Map

data_split: test


J. Japanese Game

problem_index: J

time_limit: 3 seconds

memory_limit: 512 megabytes

source: codeforces

raw_problem:
J. Japanese Game

time limit per test
3 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Joseph really likes the culture of Japan. Last year he learned Japanese traditional clothes and visual arts and now he is trying to find out the secret of the Japanese game called Nonogram.

In the one-dimensional version of the game, there is a row of $$$n$$$ empty cells, some of which are to be filled with a pen. There is a description of a solution called a profile — a sequence of positive integers denoting the lengths of consecutive sets of filled cells. For example, the profile of $$$[4, 3, 1]$$$ means that there are sets of four, three, and one filled cell, in that order, with at least one empty cell between successive sets.

A suitable solution for $$$n = 12$$$ and $$$p = [4, 3, 1]$$$.

A wrong solution: the first four filled cells should be consecutive.

A wrong solution: there should be at least one empty cell before the last filled cell.

Joseph found out that for some numbers $$$n$$$ and profiles $$$p$$$ there are lots of ways to fill the cells to satisfy the profile. Now he is in the process of solving a nonogram consisting of $$$n$$$ cells and a profile $$$p$$$. He has already created a mask of $$$p$$$ — he has filled all the cells that must be filled in every solution of the nonogram.

The mask for $$$n = 12$$$ and $$$p = [4, 3, 1]$$$: all the filled cells above are filled in every solution.

After a break, he lost the source profile $$$p$$$. He only has $$$n$$$ and the mask $$$m$$$. Help Joseph find any profile $$$p'$$$ with the mask $$$m$$$ or say that there is no such profile and Joseph has made a mistake.

Input

The only line contains a string $$$m$$$ — the mask of the source profile $$$p$$$. The length of $$$m$$$ is $$$n$$$ ($$$1 \le n \le 100\,000$$$). The string $$$m$$$ consists of symbols # and _ — denoting filled and empty cells respectively.

Output

If there is no profile with the mask $$$m$$$, output the number $$$-1$$$. Otherwise, on the first line, output an integer $$$k$$$ — the number of integers in the profile $$$p'$$$. On the second line, output $$$k$$$ integers of the profile $$$p'$$$.

Examples

Input

__#_____

Output

2
3 2

Input

_#

Output

-1

Input

___

Output

0

question:
Joseph really likes the culture of Japan. Last year he learned Japanese traditional clothes and visual arts and now he is trying to find out the secret of the Japanese game called Nonogram.
In the one-dimensional version of the game, there is a row of $$$n$$$ empty cells, some of which are to be filled with a pen. There is a description of a solution called a profile — a sequence of positive integers denoting the lengths of consecutive sets of filled cells. For example, the profile of $$$[4, 3, 1]$$$ means that there are sets of four, three, and one filled cell, in that order, with at least one empty cell between successive sets.
 ![image](1.png)A suitable solution for $$$n = 12$$$ and $$$p = [4, 3, 1]$$$.
 ![image](2.png)A wrong solution: the first four filled cells should be consecutive.
 ![image](3.png)A wrong solution: there should be at least one empty cell before the last filled cell.
Joseph found out that for some numbers $$$n$$$ and profiles $$$p$$$ there are lots of ways to fill the cells to satisfy the profile. Now he is in the process of solving a nonogram consisting of $$$n$$$ cells and a profile $$$p$$$. He has already created a mask of $$$p$$$ — he has filled all the cells that must be filled in every solution of the nonogram.
 ![image](4.png)The mask for $$$n = 12$$$ and $$$p = [4, 3, 1]$$$: all the filled cells above are filled in every solution.
After a break, he lost the source profile $$$p$$$. He only has $$$n$$$ and the mask $$$m$$$. Help Joseph find any profile $$$p'$$$ with the mask $$$m$$$ or say that there is no such profile and Joseph has made a mistake.

Input
The only line contains a string $$$m$$$ — the mask of the source profile $$$p$$$. The length of $$$m$$$ is $$$n$$$ ($$$1 \le n \le 100\,000$$$). The string $$$m$$$ consists of symbols # and _ — denoting filled and empty cells respectively.

Output
If there is no profile with the mask $$$m$$$, output the number $$$-1$$$. Otherwise, on the first line, output an integer $$$k$$$ — the number of integers in the profile $$$p'$$$. On the second line, output $$$k$$$ integers of the profile $$$p'$$$.

Examples
Input
__#_____

Output
2
3 2

Input
_#

Output
-1

Input
___

Output
0

image_tags: Patterns Patterns Patterns Patterns

data_split: test