package javacodes;
/**
 * This class is to represent a Graph and to perform some operation in Graph
 */
import java.util.*;
 

class WebGraph
{
    private int V;   
    
    private LinkedList<Integer> adj[];
   private int dist[]; 
   private int par[]; 
    
   /**
    * Constructor to create a WebGraph
    * @param v
    */
    WebGraph(int v)
    {
        V = v;
        
        adj = new LinkedList[v];
        
        dist=new int[v];
        
        par=new int[v];
        
        for (int i=0; i<v; ++i)
            
        {adj[i] = new LinkedList();
        }
    }
 
   /**
    * This is to add an edge in the WebGraph with Vertices v and Weight w
    * @param v
    * @param w
    */
    void addEdge(int v,int w)
    {
        adj[v].add(w);
    }
 
   
    /**
     * This api performs Breadth First Search in (this)WebGraph
     * @param s
     */
    void BFS(int s)
    {
        
        boolean visited[] = new boolean[V];
        
        for(int i=0;i<V;i++)
            
        {dist[i]=Integer.MAX_VALUE;
        
        par[i]=-1;
        }
       
        LinkedList<Integer> queue = new LinkedList<Integer>();
 
       
        visited[s]=true;
        
        dist[s]=0;
        
        queue.add(s);
 
        while (queue.size() != 0)
        {
           
            s = queue.poll();
          
            Iterator<Integer> i = adj[s].listIterator();
            
            while (i.hasNext())
            {
                int n = i.next();
                
                if (!visited[n])
                {
                    visited[n] = true;
                    
                    dist[n]=dist[s]+1;
                    
                    par[n]=s;
                    
                    queue.add(n);
                }
            }
        }
    }
    
    /**
	 * Thus api prints a path(showing all the vertices in between s and d
	 * vertices) from Source vertices s to Destination vertices d
	 * 
	 * @param s
	 * @param d
	 */
    void path(int s,int d)
    {
        BFS(s);
        
        System.out.print(d);
        
        int tmp=d;
        
        while(tmp!=-1&&tmp!=s){
            
        System.out.print("<-"+par[tmp]);
        
        tmp=par[tmp];
    }
        System.out.println("\nDistance form "+s+" to "+d+" is : "+dist[d]);
        
    }
    /**
     * This api prints the diameter of this WebGraph
     */
    void diameter()
    {
        int max=Integer.MIN_VALUE;
        
        for(int j=0;j<V;j++){
            
        BFS(j);
        
        for(int i=0;i<V;i++)
        {
            if(max<dist[i])
                
                max=dist[i];
        }}
        System.out.println("Diameter of Graph is : "+max);
    }
    
    public static void main(String args[])
    {
        Scanner in=new Scanner(System.in);
        
        System.out.println("Enter number of vertices:");
        
        int v=in.nextInt();int u,e;
        
        WebGraph g = new WebGraph(v);
        
        System.out.println("Enter number of edges:");
        
        e=in.nextInt();
        
        System.out.println("Enter Edges (u,v)");
        
        for(int i=0;i<e;i++)
        {
            u=in.nextInt();
            
            v=in.nextInt();
            
            g.addEdge(u, v);
        }
       g.diameter();
       
        System.out.println("\nEnter source and destination to find min distance :");
        
        int s=in.nextInt();
        
        int d=in.nextInt();
        
        g.path(s,d);
    }
}