module ArrayL = ArrayLabels
module ListL = ListLabels

let dbg = Printf.printf "[debug]%s"

let max_num = 100_000_000_000

let id = fun x -> x
let tuple2 x y = (x,y)
let tuple3 x y z = (x,y,z)
let succ x = x + 1
let pred x = x - 1

let (++) n m =
  let rec aux i =
    if i = m then [m]
    else i :: aux (i+1) in
  if n > m then [] else aux n

let (++^) n m = n ++ (m-1)

let scan fmt f = Scanf.sscanf (read_line ()) fmt f

let scan_list ~sep cnv =
  let line = read_line () in
  Str.split (Str.regexp_string sep) line
  |> List.map cnv

let scan_lines n fmt f =
  List.map (fun _ -> scan fmt f) (0++^n)

let scan_matrix n m e conv =
  let arr = Array.make_matrix n m e in
  Array.iteri (fun i line ->
      let s = Scanf.Scanning.from_string @@ read_line () in
      Array.iteri (fun j _ ->
          arr.(i).(j) <- Scanf.bscanf s " %s" conv;
        ) line) arr; arr

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let between n x m = n <= x && x < m

let string_to_list s =
  List.map (String.get s) (0 ++^ String.length s)

let n = scan "%d" id

let dfs arr pre post  =
  let m = ref 1 in
  let rec aux i =
    pre.(i) <- !m; incr m;
    ArrayL.iter arr.(i) ~f:(fun v -> if pre.(v) = 0 then aux v);
    post.(i) <- !m; incr m;
  in
  ListL.iter (1++n) ~f:(fun i -> if pre.(i) = 0 then aux i)

let () =
  let arr = Array.make (succ n) [||] in
  ListL.iter (0++^n) ~f:(fun _ ->
      let a = Array.of_list @@ scan_list ~sep:" " int_of_string in
      arr.(a.(0)) <- Array.sub a 2 a.(1));
  let pre = Array.make (succ n) 0 in
  let post = Array.make (succ n) 0 in
  dfs arr pre post;
  ListL.iter (1++n) ~f:(fun i ->
      Printf.printf "%d %d %d\n" i pre.(i) post.(i))

