#include <iostream>
#include <map>
using namespace std;
class graph  {
public:
	typedef map<int,int> edgetype ;
	graph() ;
	void add_node(int p) ;
	void add_edge(int p,int q,int v=1) ;
	void mbejar(int p) ;
	void mkeres() ;	
	int apa(int p) ;
	int d(int p) ;
	int f(int p) ;
private:	
	int i ;
	class node {
	public:
		int d,f,apa;
		edgetype edges;
	};
	map<int,node> nodes;
};
graph::graph() {
	graph::i=1 ;
}	
void graph::add_node(int p) {
	node n;
	n.d=0 ;
	n.f=0 ;
	n.apa=0 ;
	graph::nodes[p]=n ;
};
void graph::add_edge(int p, int q,int v) {
	graph::nodes[p] .edges[q]=v;
};	
int graph::apa(int p) {
	return graph::nodes[p].apa  ;
};
int graph::d(int p) {
	return graph::nodes[p].d  ;
};
int graph::f(int p) {
	return graph::nodes[p].f  ;
};
void graph::mbejar(int p) {
	edgetype::iterator q;
	graph::nodes[p].d= graph::i++ ;
	for (q=graph::nodes[p].edges.begin(); q != graph::nodes[p].edges.end(); ++q) {
		if (!graph::d(q->first)) {
			graph::nodes[q->first].apa=p ;
			mbejar(q->first);
		}	
	}
	graph::nodes[p].f= graph::i++ ;
};
void graph::mkeres() {
	map<int,graph::node>::iterator p;
	for (p=graph::nodes.begin(); p != graph::nodes.end(); ++p) {
		if (!graph::d(p->first)) mbejar(p->first) ;
	}
}