import java.util.Queue;
import java.util.LinkedList;
import java.util.Stack;
//vertex in the graph must have serial number
//from 0 to n, if graph isn't suitable for this
//write map() to map.
//directed no-weight graph
class Graph1{
	private static boolean[][] Matrix;
	private static int vertexNum;
	public static void generator(int[][] G, int vNum){
	vertexNum = vNum;
	Matrix = new boolean[vertexNum][vertexNum];
	for(int i=0;i < G.length;i++){
	Matrix[G[i][0]][G[i][1]] = true;
	}
	}
	public static boolean isRouteDFS(int v1, int v2){
	if(v1 < 0 || v2 < 0 || 
	v1 >= Matrix.length || v2 >= Matrix.length)
	return false;
	boolean[] isVisited = new boolean[vertexNum];
	Stack s = new Stack();
	int v = -1;	
	if(v1 != v2){
	s.push(v1);
	isVisited[v1] = true;
	} else
	return true;
	while(!s.empty()){
	v = s.peek();//when v's all next node have been invisted, then pop
//	System.out.println("["+v+"]");//
	
	boolean Marked = false;	
	for(int j=0;j < Matrix[v].length;j++)
	if(Matrix[v][j] && !isVisited[j])
	if(j == v2){
	return true;
	} else{
	s.push(j);
	isVisited[j] = true;
	Marked = true;
	break;
	}
	if(!Marked)
	s.pop();
	}
	return false;
	}
	public static boolean isRouteBFS(int v1, int v2){
	if(v1 < 0 || v2 < 0 || 
	v1 >= Matrix.length || v2 >= Matrix.length)
	return false;
	boolean[] isVisited = new boolean[vertexNum];	
	Queue queue = new LinkedList();
	int v = -1;
	queue.offer(v1);
	isVisited[v1] = true;
	while(!queue.isEmpty()){
	v = queue.poll();
	if(v == v2)
	return true;
	for(int j = 0;j < Matrix[v].length;j++)
	if(Matrix[v][j] == true && isVisited[j] == false)
	queue.offer(j);
	}
	return false;
	}
	public static void printMatrix(){
	for(int i=0;i < Matrix.length;i++){
	System.out.print(i+": ");
	for(int j=0;j < Matrix[i].length;j++)
	System.out.print((Matrix[i][j] == true ? 1 : 0) + " ");
	System.out.println();
	}
	}
}
public class Solution{
	public static void main(String[] args){
	int[][] G = {
	{0, 1}, {0, 2},
	{1, 3}, {1, 4},
	{2, 4},
	{4, 0}
	};
	Graph1.generator(G, 5);
	Graph1.printMatrix();
	System.out.println("R:"+Graph1.isRouteBFS(2, 3));
	System.out.println("R:"+Graph1.isRouteDFS(2, 3));
	}
}