class Solution {
    // Function to return Breadth First Traversal of given graph.
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> bfs=new ArrayList<>();
        Queue<Integer> q=new LinkedList<>();
        int[] visited=new int[V];
        
        q.add(0);
        visited[0]=1;
        while(!q.isEmpty()){
            Integer node=q.poll();
            bfs.add(node);
            for(Integer i:adj.get(node)){
                if(visited[i]==0){
                  q.add(i); 
                  visited[i]=1;
                }
            }
            
        }
        return bfs;
    }
}

class Solution {
    // Function to return a list containing the DFS traversal of the graph.
    public void dfs(ArrayList<ArrayList<Integer>> adj,ArrayList<Integer> ans,int node,int[] visited){
        visited[node]=1;
        ans.add(node);
        for(Integer i:adj.get(node)){
            if(visited[i]==0){
                dfs(adj,ans,i,visited);
            }
        }
    }
    public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> ans=new ArrayList<>();
        int[] visited=new int[V];
        dfs(adj,ans,0,visited);
        return ans;
        
    }
}

class Solution {
    private boolean dfsCheck(int node, ArrayList<ArrayList<Integer>> adj, int vis[], int pathVis[]) {
        vis[node] = 1; 
        pathVis[node] = 1; 
        
        // traverse for adjacent nodes 
        for(int it : adj.get(node)) {
            // when the node is not visited 
            if(vis[it] == 0) {
                if(dfsCheck(it, adj, vis, pathVis) == true) 
                    return true; 
            }
            // if the node has been previously visited
            // but it has to be visited on the same path 
            else if(pathVis[it] == 1) {
                return true; 
            }
        }
        
        pathVis[node] = 0; 
        return false; 
    }

    // Function to detect cycle in a directed graph.
    public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
        int vis[] = new int[V];
        int pathVis[] = new int[V];
        
        for(int i = 0;i<V;i++) {
            if(vis[i] == 0) {
                if(dfsCheck(i, adj, vis, pathVis) == true) return true; 
            }
        }
        return false; 
    }
}

class Solution
{
    static void dfs(int V,ArrayList<ArrayList<Integer>> adj,int[] visited,int i,Stack<Integer> st){
        visited[i]=1;
        for(int j:adj.get(i)){
            if(visited[j]==0){
                dfs(V,adj,visited,j,st);
            }
        }
        st.add(i);
    }
    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        Stack<Integer> st=new Stack<>();
        int[] visited=new int[V];
        for(int i=0;i<V;i++){
            if(visited[i]==0){
                dfs(V,adj,visited,i,st);
            }
        }
        int[] ans=new int[V];
        for(int i=0;i<V;i++){
            ans[i]=st.pop();
        }
        return ans;
    }
}

class Solution
{
    //Function to return list containing vertices in Topological order. 
    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        //Kahn Algorithm Approach(BFS)
        //starting nodes will be those with indegree 0 because there is no node coming before them
        //put them in Q, and then keep reducing indegree values in array and put them in Q when their
        //indegree becomes 0 , visited array is not needed because we are visiting a node only if its
        //indegree becomes 0 that means it will never be visited again
        int[] topo=new int[V];
        int counter=0;
        Queue<Integer> q=new LinkedList<>();
        int[] indegree=new int[V];
        for(int i=0;i<V;i++){
            for(int j:adj.get(i)){
                indegree[j]+=1;
            }
        }
        //now starting nodes will be put in Q
        for(int i=0;i<V;i++){
            if(indegree[i]==0){
                q.offer(i);
            }
        }
        //now bfs 
        while(!q.isEmpty()){
            int node=q.poll();
            topo[counter]=node;
            counter++;
            for(int j:adj.get(node)){
                indegree[j]--;
                if(indegree[j]==0){
                    q.offer(j);
                    
                }
            }
        }
        return topo;
    }
}

class Pair{
    int dist;
    int node;
    Pair(int dist,int node){
        this.dist=dist;
        this.node=node;
    }
}
class Solution
{
    //Function to find the shortest distance of all the vertices
    //from the source vertex S.
    static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
    {
        int[] ans=new int[V];
        Arrays.fill(ans,Integer.MAX_VALUE);
        PriorityQueue<Pair> pq=new PriorityQueue<Pair>((x,y)->x.dist-y.dist); //minheap
        ans[S]=0;
        pq.offer(new Pair(ans[S],S));
        while(pq.size()!=0){
            Pair temp=pq.poll();
            for(ArrayList<Integer> it:adj.get(temp.node)){
                if(it.get(1)+ans[temp.node]<ans[it.get(0)]){
                    ans[it.get(0)]=it.get(1)+ans[temp.node];
                    pq.offer(new Pair(ans[it.get(0)],it.get(0)));
                }
            }
        }
        return ans;
    }
}

class Solution {
    static int[] bellman_ford(int V, ArrayList<ArrayList<Integer>> edges, int S) {
        // for negative edges no need to make adjacency list
        //only for directed graphs
        int[] dist=new int[V];
        for(int i=0;i<dist.length;i++){
            dist[i]=(int)Math.pow(10,8);
        }
        dist[S]=0;
        for(int i=1;i<=V;i++){
           for(int j=0;j<edges.size();j++){
               int src=edges.get(j).get(0);
               int dest=edges.get(j).get(1);
               int wt=edges.get(j).get(2);
               if(i<V && dist[src]!=(int)Math.pow(10,8)&& (wt+dist[src]<dist[dest])){
                   dist[dest]=wt+dist[src];
               }
               else if(i==V && dist[src]!=(int)Math.pow(10,8) && (wt+dist[src]<dist[dest])){
                   int[] temp=new int[1];
                   temp[0]=-1;
                   return temp;
               }
           }
            
        }
        return dist;
    }
}

class Solution
{
    public void shortest_distance(int[][] matrix)
    {
        //use floyd warshall when we have to find shortest distance of all nodes to all other
        //nodes it can detect negative cycles and it can also 
         for(int i=0;i<matrix.length;i++){
             for(int j=0;j<matrix[0].length;j++){
                 if(matrix[i][j]==-1){
                     matrix[i][j]=(int)(1e9);
                 }
                 if(i==j){
                     matrix[i][j]=0;
                 }
             }
         }
         for(int via=0;via<matrix.length;via++){
             for(int i=0;i<matrix.length;i++){
                 for(int j=0;j<matrix[0].length;j++){
                     matrix[i][j]=Math.min(matrix[i][j],matrix[i][via]+matrix[via][j]);
                 }
             }
         }
         for(int i=0;i<matrix.length;i++){
             for(int j=0;j<matrix[0].length;j++){
                 if(matrix[i][j]==(int)(1e9)){
                     matrix[i][j]=-1;
                 }
             }
         }
    }
}