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.io.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Main m = new Main();
		m.input();
		m.solve();
		m.output();
	}
	
//	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	InputUtil in = new InputUtil();
	PrintWriter out = new PrintWriter(System.out);
	
	int n = 0;
	ArrayGraph<NodeValue> g = new ArrayGraph<>();
	
	public void input() throws IOException {
		n = in.nextInt();
		g.init(n);
		for(int i=0; i<n; i++) {
			int v = in.nextInt();
			int k = in.nextInt();
			int[] adj = in.nextInt(new int[k]);
			g.addVertice(v, adj, 0, k);
		}
	}

	public void solve() throws IOException {
		int t = 0;
		for(int i=1; i<=n; i++) {
			t = dfs(i,t);
		}
	}
	
	public void output() {
		for(int i=1; i<=n; i++) {
			out.print(i);
			out.print(' ');
			out.print(g.getValue(i).d);
			out.print(' ');
			out.println(g.getValue(i).f);
		}
		out.flush();
	}
	
	private int dfs(int nodeId, int timestamp) {
		NodeValue nv = g.getValue(nodeId);
		if(nv == null) {
			nv = new NodeValue();
			nv.d = ++timestamp;
			g.setValue(nodeId,nv);
			for(int adjNodeId: g.getAdjNode(nodeId)){
				timestamp = dfs(adjNodeId,timestamp);
			}
			nv.f = ++timestamp;
		}
		return timestamp;
	}
	
}

class NodeValue {
	int d = 0;
	int f = 0;
}

class ArrayGraph<T> {

	int[][] adj = null;
	List<T> value = null;
	
	public ArrayGraph() {}
	
	public void init(int nodeMax) {
		adj = new int[nodeMax+1][];
		value = new ArrayList<>(nodeMax+1);
		for(int i=0; i<=nodeMax; i++) {
			value.add(null);
		}
	}
	
	public void addVertice (int nodeId, int[] adjNode, int adjNodeoffset, int adjNodeLen) {
		adj[nodeId] = Arrays.copyOfRange(adjNode, adjNodeoffset, adjNodeLen);
	}
	
	public int[] getAdjNode (int nodeId) {
		return (adj == null || adj.length <= nodeId ) ? null : adj[nodeId];
	}
	
	public T getValue(int nodeId) {
		return (value == null || value.size() <= nodeId) ? null : value.get(nodeId);
	}

	public void setValue(int nodeId, T v) {
		value.set(nodeId,v);
	}
}


class InputUtil {
	//Static Fields
	private static final int BUFSIZ = 100000;
	
	//Fields
	protected InputStream in;
	private byte[] buf = null;
	private int ptr = 0;
	private int max = -1;
	private DataInputStream dis = null;
	//Constructors
	public InputUtil() {this(System.in,BUFSIZ);}
	public InputUtil(InputStream in, int bufsiz) {
		initBuf(bufsiz);
		initIn(in);
	}
	
	//Methods
	//Initializer
	protected void initIn(InputStream in) {dis = new DataInputStream(this.in = in);}
	protected void initBuf(int bufsiz) {buf = new byte[bufsiz];}
	
	//buffer operation
	private void next() throws IOException {ptr++; readBuf();}
	private void readBuf() throws IOException {
		if(ptr >= max && dis.available()>0) {
			if(max>0) Arrays.fill(buf,0,max,(byte)0);
			max = dis.read(buf);
			ptr = 0;
		}
	}
	
	//Number Input Reader/Parser
	private boolean isNum(byte b) {return '0' <= b && b <= '9'; }
	private boolean isMinus(byte b) {return b=='-'; }

	private int _nextInt() throws IOException {
		int sign = 1;
		int res = 0;
		byte c;
		while (!isNum(c=buf[ptr]) && !isMinus(c)) 
			next();
		if (isMinus(buf[ptr])) {
			sign = -1;
			next();
		}
		while (isNum(c=buf[ptr])) {
			res *= 10;
			res += c - '0' ;
			next();
		}
		next();
		return sign * res;
	}
	
	public int nextInt() throws IOException {
		readBuf();
		return _nextInt();
	}

	public int[] nextInt(int[] result) throws IOException {
		readBuf();
		for(int i=0; i<result.length; i++) {
			result[i] = _nextInt();
		}
		return result;
	}
	
	//Close 
	public void close() throws IOException {
		if(!this.in.equals(System.in)) 
			this.in.close();
	}

}