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.

Constraints

* $1 \leq n \leq 100$

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.

Examples

Input

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


Output

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


Input

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


Output

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

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	ArrayList<Vertex> undiscovered = new ArrayList<>(); // What we haven't searched yet. 
	ArrayList<Vertex> vertices = new ArrayList<>(); // We will use this to access the time values at the end
	int time = 1;	
	
	public static void main(String[] args) {
			
		Main test = new Main();
		Scanner in = new Scanner(System.in);
		int n = Integer.parseInt(in.nextLine());
		// Initialize the vertices for the specified number of vertices. (Neighbors are not set yet)
		for (int i = 0; i < n; i++) {
			Vertex v = new Vertex(i + 1);
			test.undiscovered.add(v);
			test.vertices.add(v);
		}
		
		// Now we will initialize the neighbors by reading through our input lines
		for (int i = 0; i < n; i++) {
			String[] holder = in.nextLine().split(" ");
			Vertex v = test.undiscovered.get(Integer.parseInt(holder[0]) - 1);
			for (int j = 2; j < holder.length; j++) {
				Vertex neighbor = test.undiscovered.get(Integer.parseInt(holder[j]) - 1);
				v.addNeighbor(neighbor);
			}
		}
		for (Vertex v : test.vertices) {
			test.depthFS(v);
		}		
		for (Vertex v : test.vertices) {
			System.out.println(v.value + " " + v.dv + " " + v.df);
		}
		
		
	}
	
	public void depthFS(Vertex curr) {
		
		// We start by making sure that we still have undiscovered nodes
		if (undiscovered.isEmpty()) {
			return; // If it's empty, then we are done
		}
		
		// Now we check to make sure we haven't already seen the current node. ie. If it's not in undiscovered, we break
		if (curr.disc) {
			return; // We've already seen the node, so we break
		}

		// This node has been discovered now
		this.undiscovered.remove(curr);
		curr.disc = true;
		
		// Now we set the discovery value of the current node to our current time
		curr.dv = time;
		time += 1;
		// Now we are going to expand curr and go through its children
		for (Vertex child : curr.neighbors) {
			this.depthFS(child);
		}		
		curr.df = time;
		time += 1;
	}
	
	
}

class Vertex {
	public ArrayList<Vertex> neighbors = new ArrayList<>();
	public int value;
	public int dv;
	public int df;
	public boolean disc;
	
	public Vertex(int val) {
		value = val;
		disc = false;
	}
	
	public void addNeighbor (Vertex n) {
		neighbors.add(n);
	}
	
	public String toString() {
		return "" + this.value + " " + this.dv + " " + this.df;
	}
}

