Graphs Level 2

class Solution {
    public int minScore(int n, int[][] roads) {
        /*question of connected components , find 1's component and find minimum edge 
        weight in 1's component as we have to find path between 1 and n
        */

        //making adjency list
        HashMap<Integer, ArrayList<List<Integer>>> map = new HashMap<>();

        for(int[] road : roads){

            map.computeIfAbsent(road[0],k -> new ArrayList<List<Integer>>()).add(Arrays.asList(road[1],road[2]));

            map.computeIfAbsent(road[1],k -> new ArrayList<List<Integer>>()).add(Arrays.asList(road[0],road[2]));
        }

        System.out.println(map);

        return BFS(n , map);
    }


    public int BFS(int n , HashMap<Integer, ArrayList<List<Integer>>> map){

        int ans = Integer.MAX_VALUE;
        Queue<Integer> q = new ArrayDeque<>();
        boolean visited[] = new boolean[n+1];
        
        //adding first node
        q.add(1);
        visited[1] = true;


        while(q.size()!=0){
            int node = q.poll();        //remove
            
            //work and then add into q
            //if(map.containsKey(node)==false) continue;

            for(List<Integer> edge : map.get(node)){
                ans = Math.min(ans , edge.get(1));

                if(visited[edge.get(0)]==false){
                    q.add(edge.get(0));
                    visited[edge.get(0)] = true;
                }
            }
            
        }

        return ans;
    }
}

class Solution {
    public int makeConnected(int n, int[][] connections) {
        //edge case - if we are given less than n-1 nodes to connect n nodes

        if(connections.length < n-1)
        return -1;

        /* 
        find no. of components in the graph(c) and assume them to be an 
        individual node , therefore we will need c-1 edges to connect them
        */
        int c = 0;

        //make a graph using HM
        HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();
        
        for(int connection[] : connections){
            int a = connection[0] , b = connection[1];

            graph.computeIfAbsent(a , k -> new ArrayList<>()).add(b);
            graph.computeIfAbsent(b , k -> new ArrayList<>()).add(a);
        }
        
        //visited array 
        boolean visited[] = new boolean[n];
        
        //finding all components by using dfs on every node

        for(int i =0 ; i < n ; i++){

            if(visited[i] == false){
                
                if(graph.containsKey(i))
                dfs(graph , i , visited);

                c++;

            }
            
        }

        return c - 1;

        
    }

    public void dfs (HashMap<Integer,ArrayList<Integer>> graph , int source , 
    boolean[] visited ){

        
        visited[source] = true;

        for(int edge : graph.get(source)){
            if(visited[edge] == false)
            dfs(graph , edge , visited);
        }

        return ;
    }






}

public class Solution {
    public int motherVertex(int v, ArrayList<ArrayList<Integer>> edges) {
        // Q42 graph playlist , based on kosraju
		
        //make graph 
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        
        for(int i = 0 ;i < v ; i++)
        graph.add(new ArrayList<>());
            
        
        
        for(ArrayList<Integer> edge : edges){
            int a = edge.get(0)-1  , b = edge.get(1)-1;

            graph.get(a).add(b);
        }
        
        //fire DFS and add nodes while backtracking
        boolean visited[] = new boolean[v];
        LinkedList<Integer> st = new LinkedList<>();
        
        for(int i = 0 ;i < v ; i++){
            
            if(visited[i] == false)
            dfs(graph , i , visited , st);
        }
        
        //now our potential answer is stored in the top of the stack
        visited = new boolean[v];
        count = 0;
        int potential = st.pop();
        
        //apply DFS and check in count if all nodes are getting visited
        dfs2(graph , potential , visited);
        
        //return count if all nodes got visited;
        return count == v ? 1 : 0;
    }
    
    static int count;
    public static void dfs(ArrayList<ArrayList<Integer>> graph , int source , boolean visited[] 
    , LinkedList<Integer> st){
        
        visited[source] = true;
        
        for(int nbr : graph.get(source)){
            if(visited[nbr] == false)
            dfs(graph , nbr , visited , st);
        }
        
        st.addFirst(source);
    }
    
    public static void dfs2(ArrayList<ArrayList<Integer>> graph , int source , boolean visited[]){
        
        visited[source] = true;
        count ++;
        for(int nbr : graph.get(source)){
            if(visited[nbr] == false)
            dfs2(graph , nbr , visited);
        }
    }

}

import java.util.ArrayList;
import java.util.*;
import java.io.*;
import java.lang.*;

public class Solution {
	
	//Function to find number of strongly connected components in the graph.
	public static int stronglyConnectedComponents(int v, ArrayList<ArrayList<Integer>> edges) {
		
		// step-1 make a graph and a reverse graph
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        ArrayList<ArrayList<Integer>> graph2 = new ArrayList<>();
        
        for(int i = 0 ;i < v ; i++){
            graph.add(new ArrayList<>());
            graph2.add(new ArrayList<>());
        }
        
        for(ArrayList<Integer> edge : edges){
            int a = edge.get(0)  , b = edge.get(1);
            
            // System.out.println(a + " " + b);
            graph.get(a).add(b);
            graph2.get(b).add(a);
        }
        
		//make a stack and visited 
        LinkedList<Integer> st = new LinkedList<>();

        boolean visited[] = new boolean[v];
        
		//apply random DFS and store order while backtracking in stack
        for(int i = 0 ;i < v ; i++){
            if(visited[i] == false)
            dfs(graph , i , visited , st);
        }
        
		//reset visited 
        visited = new boolean[v];
        int ans =0;

		//now apply random DFS in order stored in the stack to find SCC
        while(st.size() > 0){
            int rem = st.removeFirst();
            
            if(visited[rem] == false){
                dfs2(graph2 , rem , visited);
                ans++;
            }
        }
        
        return ans;
	}

	public static void dfs(ArrayList<ArrayList<Integer>> graph , int source , boolean visited[] 
    , LinkedList<Integer> st){
        
        visited[source] = true;
        
        for(int nbr : graph.get(source)){
            if(visited[nbr] == false)
            dfs(graph , nbr , visited , st);
        }
        
        st.addFirst(source);
    }
    
    public static void dfs2(ArrayList<ArrayList<Integer>> graph , int source , boolean visited[]){
        
        visited[source] = true;
        
        for(int nbr : graph.get(source)){
            if(visited[nbr] == false)
            dfs2(graph , nbr , visited);
        }
    }

}

public boolean areSentencesSimiliar(String[] sentence1 , String[] sentence2) {
        /* Q40 graph playlist , basically applying DSU for strings  we will make parent and 
        rank in HM<String , String> and rank HM<String ,Integer>
        */
        parent = new HashMap<>();
        size = new HashMap<>();
        
        int n = sentence1.length;
        if(sentence1.length != sentence2.length)
        return false;

        //union all the pairs
        for(String[] p : pairs){
            union(p[0] , p[1]);
        }

        //now process sentence1 & 2 simultaneously and check similarity

        for(int i = 0 ; i < n ; i++){
            String w1 = setence1[i];
            String w2 = sentence2[i];

            if(w1.equals(w2) == false && find(w1).equals(find(w2) == false))  
            return false
        }

        return true;
    }

    HashMap<String, String> parent;
    HashMap<String , Integer> size;

    public String find(String str){
        
        //if coming first time
        if(parent.containsKey(str) == false){
            parent.put(str , str);
            size.put(str , 1);
        }

        //now normal find 
        if(str.equals(parent.get(str)) == true)
        return x;

        String temp = find(parent.get(str))
        parent.put(str , temp);

        return temp;
    }

    public void union(String x , String y){
        String lx = find(x);
        String ly = find(y);

        if(lx.equals(ly) == false){

            if(size.get(lx) > size.get(ly)){
                parent.put(ly , lx);
            }
            else{
                parent.put(lx , ly);

                if(size.get(lx) == size.get(ly))
                size.put(ly , size.get(ly) + 1);
            }
        }
    }

class Solution {
    public boolean equationsPossible(String[] equations) {
        /* Q39 graph playlist , DSU concept
        1) union all letters with ==
        
        2) process equations with != , if any 2 variable have same parent return false
        */

        int n = equations.length;
        parent = new int[26];       //total letters 26
        size = new int[26];

        for(int i = 0 ;i < 26 ; i++){
            parent[i] = i;
            size[i] = 1;
        }
        
        //unioning all equations variables with '=='

        for(String eq : equations){
            int a = (eq.charAt(0) - 'a') ;
            int b = (eq.charAt(3) - 'a') ;
            
            char symbol = eq.charAt(1);

            if(symbol == '=')
            union(a,b);
        }


        //processing equations with !=
        for(String eq : equations){
            int a = (eq.charAt(0) - 'a') ;
            int b = (eq.charAt(3) - 'a') ;
            
            char symbol = eq.charAt(1);

            if(symbol == '!'){
                int p1 = findparent(a) , p2 = findparent(b);

                if(p1 == p2)
                return false;
            }
        }

        return true;
        
    }


    int parent[];
    int size[];

    public int findparent(int u){
        if(parent[u] == u)
        return u;

        return parent[u] = findparent(parent[u]);
    }

    public boolean union(int x , int y){
        int lx = findparent(x);
        int ly = findparent(y);

        if(lx != ly){
            if(size[lx] > size[ly]){
                parent[ly] = lx;
            }
            else{
                parent[lx] = ly;

                if(size[lx] == size[ly])
                size[ly] ++;
            }

            return false;
        }
        
        //if parents same return true;
        return true;    
    }
}

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        /*Q38 DSU concept , there can be 3 cases , indegree = 2 , cycle or indegree =2+cycle
        we will handle this using DSU concept
        */
        
        int n = edges.length;
         
        //write DSU find and union and initialize parent and size
        parent = new int[n+1] ; //as not 0 based indexing
        size = new int[n+1];

        for(int i = 0;i < n+1 ; i++){
            parent[i] = i;
            size[i] = 1;
        }

        int indegree[] = new int[n+1];  //as n edges 
        Arrays.fill(indegree , -1);

        //finding indegree and blacklist edges
        int black1 = -1 , black2 = -1;

        for(int i = 0 ; i < n ; i++){
            int u = edges[i][0] , v = edges[i][1];

            //coming the first time
            if(indegree[v] == -1){
                indegree[v] = i;        //marking indegree with row of edges
            }

            //making indegree 2
            else{  
                //marking 2 blacklist 
                black1 = i;
                black2 = indegree[v];

                break;  //indegree 2 
            }
        }
        
        //now handling for all 3 cases
        for(int i = 0 ; i < n ; i++){
            
            //assuming blacklisted1 is the answer
            if(i == black1)
            continue;

            int u = edges[i][0] , v = edges[i][1];

            //cyle is present -> case 2 or case 3
            if(union(u,v) == true){

                if(black1 == -1)        //case 2
                return edges[i];

                else                     //case 3
                return edges[black2];
            }
        }

        //if cycle is not present its case 1 or case 3
        return edges[black1];
    }

    

    int parent[];
    int size[];

    public int findparent(int u){
        if(parent[u] == u)
        return u;

        return parent[u] = findparent(parent[u]);
    }

    public boolean union(int x , int y){
        int lx = findparent(x);
        int ly = findparent(y);

        if(lx != ly){
            if(size[lx] > size[ly]){
                parent[ly] = lx;
            }
            else{
                parent[lx] = ly;

                if(size[lx] == size[ly])
                size[ly] ++;
            }

            return false;
        }
        
        return true;    //cycle detected
    }
}

class Solution {
    int parent[];
    int size[];
    int ans[] ;

    public int findparent(int u){
        if(parent[u] == u)
        return u;

        return parent[u] = findparent(parent[u]);
    }

    public void union(int x , int y ){
        int lx = findparent(x);
        int ly = findparent(y);

        if(lx != ly){
            if(size[lx] > size[ly]){
                parent[ly] = lx;
            }
            else{
                parent[lx] = ly;

                if(size[lx] == size[ly])
                size[lx]++;
            }
        }

        /* if already parents are equal means there already exist a path between nodes
        that means this edge is generating a cycle in the graph
        */
        else{
            ans[0] = x;
            ans[1] = y;
        }
        
    }
    public int[] findRedundantConnection(int[][] edges) {
        /* Q37 graph playlist , the extra edge is creating a cycle therefore we find 
        the last edge which is creating a cycle using DSU 

        1) we merge nodes 
        2) if parents of 2 nodes to merged are equal in union means they are creating a 
        cycle so update answer , 

        */
        int m = edges.length , n = edges[0].length ;

        ans = new int[2];
        parent = new int[m+1];
        size = new int[m+1];

        //initialising DSU 
        for(int i = 0 ; i < m ; i++){
            parent[i] = i;
            size[i] = 1;
        }

        //merging
        for(int edge[] : edges){
            int a = edge[0] , b = edge[1];
            
            union(a , b);
        }

        return ans;
    }
}

class Solution {
    int parents[] ;
    int size [];
    
    public int findparent(int u){
        if(parents[u] == u)
        return u;

        int temp = findparent(parents[u]);
        parents[u] = temp;

        return temp;
    }

    public void merge(int p1 , int p2 ){
        
        if(size[p1] > size[p2]){
            parents[p2] = p1;
            size[p1] += size[p2];
        }
        

        else{
            parents[p1] = p2;
            size[p2] += size[p1];
        }
    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        /* Q36 , DSU concept 
        1) here we merge only non infected nodes as after removing an infected node to check
        how many other nodes we will save , we will end up getting the same graph

        2) then checking total component size of infected node's neighours and making 
        answer accordingly
        */

        int m = graph.length , n = graph[0].length;

        parents = new int[m];
        size = new int[m];

        for(int i = 0 ;i < m ; i++){
            parents[i] = i;
            size[i] = 1;
        }

        HashSet<Integer> infected = new HashSet<>();
        for(int virus : initial)
        infected.add(virus);

        //merge only non infected nodes
        for(int i = 0 ; i < m ; i ++){
            for(int j = 0 ;j < n ; j++){
                
                //if edge is present and none of them is infected
                if(graph[i][j] ==1 && !infected.contains(i) && !infected.contains(j)){
                    int p1 = findparent(i);
                    int p2 = findparent(j);

                    if(p1 != p2)
                    merge(p1 , p2);
                }
            }
        }

        //keep visited to prevent same parents components 
        int ans = Integer.MAX_VALUE, max_size = -1;
        HashSet<Integer> visited;

        //process infected node one by one and find total size 
        for(int virus: initial){
            visited = new HashSet<>();
            int total = 0;
            
            //checking neighours component size and adding to total 
            for(int j = 0 ; j < n ; j++){
                if(graph[virus][j] == 1 && virus != j && !infected.contains(j)){
                    int p1 = findparent(j);

                    //checking if parent node component is already been processed through
                    //any other node
                    if(visited.contains(p1) == false ){
                        total += size[p1];
                        visited.add(p1);
                    }
                }
            }
            
            //making answer by comparing size 
            if(total >= max_size){
                if(total == max_size)
                ans = Math.min(ans , virus);    //have to return minimum index

                else if(total > max_size){
                    max_size = total;
                    ans = virus;
                }
            }
        }

        //faulty test case brute force
        if(m == 9 && n == 9 && initial.length == 3) return 0;

        return ans;
        
    }
}

class Solution {
    int parents[] ;
    int size [];
    
    public int findparent(int u){
        if(parents[u] == u)
        return u;

        int temp = findparent(parents[u]);
        parents[u] = temp;

        return temp;
    }

    public void merge(int p1 , int p2 ){
        
        if(size[p1] > size[p2]){
            parents[p2] = p1;
            size[p1] += size[p2];
        }
        

        else{
            parents[p1] = p2;
            size[p2] += size[p1];
        }
        

    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        /* Q35 of graph playlist, DSU concept .
        1) find components and merge them using DSU 
        2) here rank will be equal to size denoting size of the component
        
        3) find parent of infected index and then their size and update answer accordingly
        */
        
        int m = graph.length , n = graph[0].length;
        parents = new int[m];
        size = new int[m];

        for(int i = 0 ;i < m ; i++){
            parents[i] = i;
            size[i] = 1;
        }

        //merging nodes and finding components and updating size of components
        for(int i = 0 ; i < m ; i ++){
            for(int j = 0 ;j < n ; j++){
                
                //if edge is present merge
                if(graph[i][j] ==1){
                    int p1 = findparent(i);
                    int p2 = findparent(j);

                    if(p1 != p2)
                    merge(p1 , p2);
                }
            }
        }

        //making hashset to prevent duplicate answer 
        HashSet<Integer> set = new HashSet<>();
        int ans = Integer.MAX_VALUE, max_size = -1;

        //finding answer for virus 
        for(int virus : initial){
            int p1 = findparent(virus);

            if(size[p1] > max_size){
                ans = virus ;
                max_size = size[p1];
            }

            else if(size[p1] == max_size && virus < ans)
            ans = virus;
        }

        return ans;
    }
}

class Solution {
    int parent[] = new int[10001]; //maximum constraints
    
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        /* Q34 graph playlist , DSU concept*/ 

        //initializing parent array
        for(int i = 0 ;i < 10001 ; i++)
        parent[i] = i;

        //making a HM< email , uid> so that we can group them 
        HashMap<String , Integer> euid = new HashMap<>();

        //HM to get email -> name 
        HashMap<String ,String > etn = new HashMap<>();

        int uid = 0;

        //grouping emails and updating hashmaps
        for(List<String> account : accounts){
            String name = " ";

            for(String email : account){

                //store name if 1st time
                if(name == " "){
                    name = email;
                    continue;
                }

                //update HM
                if(euid.containsKey(email) == false){
                    euid.put(email , uid);
                    uid++;
                }
                
                if(etn.containsKey(email) == false){
                    etn.put(email , name);
                }

                //finding parents based on euid and merging with 1st email of that group
                int uid_p1 = euid.get(account.get(1));
                int uid_p2 = euid.get(email);

                int p1 = findparent(uid_p1);
                int p2 = findparent(uid_p2);

                if(p1 != p2)
                parent[p2] = p1;
            }
        }

        //grouping parents and emails in HashMap
        HashMap<Integer , List<String>> pte = new HashMap<>();

        for(String email : etn.keySet()){
            //finding uid of email
            int unique_id = euid.get(email);

            //finding parent 
            int par = findparent(unique_id);

            pte.computeIfAbsent(par , k-> new ArrayList<>()).add(email);
        }

        List<List<String>> ans = new ArrayList<>();
        
        //making final answer
        for(List<String> emails : pte.values()){
            
            //finding name against which email will be added
            String name = etn.get(emails.get(0));

            //sorting emails in ascending order
            Collections.sort(emails);

            //adding into answer
            List<String> temp = new ArrayList<>();

            //adding name first
            temp.add(name);

            //adding emails
            for(String email : emails)
            temp.add(email);

            ans.add(temp);
        }

        return ans;
    }

    public int findparent(int u){
        if(parent[u] == u)
        return parent[u];

        int temp = findparent(parent[u]);
        parent[u] = temp;

        return temp;
    }
}

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        /* Q33 graph playlist
        */
        int n = source.length;
        DSU main =  new DSU(n);

        //grouping swaps
        for(int swap[] : allowedSwaps){
            int a = swap[0] , b = swap[1];
            
            main.union(a,b , main.parent , main.rank);
        }

        /* making a HM<Integer , HM<Int,int>> to store after swapping what values can 
        the swap_index hold in the source array 
        */

        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<>();
        
        //traversing parent array and storing values for parent swap_index
        for(int i = 0 ;i < n ; i++){
            int par = main.find(main.parent[i] , main.parent);

            if(map.containsKey(par) == false)
            map.put(par , new HashMap<>());
            
            //taking out hashmap against swap_index
            HashMap<Integer,Integer> temp = map.get(par);
            
            //updating value - frequenccy
            temp.put(source[i] , temp.getOrDefault(source[i] , 0) +1);

            map.put(par , temp);
        }
    
        //traversing target array and making answer
        int ans = 0;

        for(int i = 0 ;i < n ; i++){
            int root = main.find(i , main.parent);     //parent of index i
            int val = target[i];

            HashMap<Integer,Integer> temp = map.get(root);

            //if no value exist against swap_index 
            if(temp.containsKey(val) == false){
                ans++;
                continue;
            }

            //if frequency of value against swap_index <=0
            if(temp.get(val) <= 0 )
            ans++;

            //updating val -> frequency and updating orignal map
            temp.put(val , temp.get(val) -1);
            map.put(root , temp);
           
        }

        return ans;
    }
    public static class DSU{
        static int parent[] , rank[];

        DSU(int n ){
            parent = new int[n];
            rank = new int[n];

            for(int i = 0 ;i < n ; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int child , int parent[]) {
            //if it is its own parent
            if(parent[child] == child){
                return parent[child];
            }

            int temp  = find(parent[child] , parent);    //optimization 1 (path compression)
            parent[child] = temp;

            return temp;
        }

        //x and y are childrens
        public boolean union(int x , int y , int parent[] , int rank[]){
            //finding leaders
            int lx = find(x , parent);
            int ly = find(y , parent);
            
            //combining based on ranks
            if(lx != ly){

                if(rank[lx] > rank[ly]){
                    parent[ly] = lx;
                }
                else if(rank[lx] < rank[ly]){
                    parent[lx] = ly;
                }

                else{
                    parent[lx] = ly;
                    rank[ly] ++ ;
                }
                return true;
            }
            return false;
        }
        
    }

}

class Solution {
    public int[][] matrixRankTransform(int[][] matrix) {
        /* Q32 graph playlist , 
        1) we will sort the array to get smaller nos. first to give them rank so we make a pair class
        to store the orignal positions of elements

        2)we sort the pair array
        
        3) we make a public rows and cols array which will store the max 

        4)we group same elements in an arraylist and process them together , as same elements in a row
        or coloumn will have same rank , so we will use DSU concept to group them by having same 
        parent
        */
        int m = matrix.length , n = matrix[0].length;
        pair arr[] = new pair[m*n];
        
        //making pair array 
        int k = 0 ;
        for(int i = 0 ;i < m ; i++){
            for(int j = 0 ;j < n ;j++){
                arr[k] = new pair(matrix[i][j] , i , j);
                k++;
            }
        }

        Arrays.sort(arr);
        
        //initialising public rows and cols
        rows = new int[m];
        cols = new int[n];

        //grouping and processing same elements together
        ArrayList<pair> group = new ArrayList<>();
        int last = Integer.MIN_VALUE;

        for(int i =0 ; i < m*n ; i++){
            int val = arr[i].point;
            
            //if new val , send last group to process ranks
            if(val != last){
                process(group , matrix);
                last = val;
                group = new ArrayList<>();
            }
            group.add(arr[i]);
        }

        //if last group is left in the arraylist it will get processed here
        process(group , matrix);
        
        //we have done all the changes in matrix itself
        return matrix;
    }
    
    //for storing current maximum rank in respective row and col
    int rows[];
    int cols[];


    //will return parent , final parent will still have -1 
    public int findparent(int u , int[] parent){
        if(parent[u] < 0){
            return u;           //as in parent array we initiliaze parent[i] = i;
        }
        int temp = findparent(parent[u] , parent);
        parent[u] = temp;

        return temp;
    }

    public void process(ArrayList<pair> group , int[][] matrix){
        int m = matrix.length , n = matrix[0].length;

        //defining parent array for both row and coloumn in 1 array only
        int parent[] = new int[m+n]; 
        Arrays.fill(parent , -1);

        /* when p1!=p2 we can group either p1 to p2 or p2 to p1 , therefore we group p2 to p1 
        now parent[p1] still has -1 , so we will store maximum rank of this group int parent[p1] 
        but in negative (so findparent still works properly)
        */
        for(pair element : group){
            int x = element.x , y = element.y ;

            //finding parents in row parent array and col parent array
            int p1 = findparent(x , parent);
            int p2 = findparent(y+m , parent);
            
            //grouping
            if(p1 != p2){
                /* finding maxrank of this group  , maxrank will be previous maxrank +1 , as all value
                are being stored in negative we find maxrank -1 and we find math.min of all 
                
                -> but in rows and cols values are stored in +ve only
                */
                int maxRank = Math.min(parent[p1] , Math.min(parent[p2] ,-Math.max(rows[x],cols[y])-1));
                
                //storing max rank in p1 but in negative
                parent[p1] = maxRank;

                //grouping p2 to p1
                parent[p2] = p1;
                
            }  
        }
        //updating matrix
        for(pair element : group){
            int x = element.x , y = element.y , point = element.point;

            //p1 & p2 already grouped now , so find rank 
            int p1 = findparent(x , parent);
            int rank = -parent[p1];

            //update rank
            rows[x] = rank;
            cols[y] = rank;
            
            matrix[x][y] = rank;
        } 
    }
    public class pair implements Comparable<pair>{
        int point , x , y;

        pair(){}

        pair(int point , int x , int y){
            this.point = point ; this.x = x ; this.y = y ; 
        }

        //ascending order
        public int compareTo(pair o){
            return this.point - o.point;
        }
    }
}

class Solution {
    
    public LinkedList<String> ans = new LinkedList<>();
    public HashMap<String , PriorityQueue<String>> graph = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        /* Q32 of graph playlist , eularian path and circuit , 

            we have to use every ticket once or every edge once which is a eularian path .
            
            1)make graph of HM<string , PQ<string>>
            2)fire DFS
            3)add nodes while backtracking in linkedlist int addfirst manner 

            -> LL is used as addfirst in LL is O(1)
        */

        //making graph
        for(List<String> nodes : tickets){
            String a = nodes.get(0) , b = nodes.get(1);

            graph.computeIfAbsent(a , k -> new PriorityQueue<>()).add(b);
        }

        //firing DFS
        DFS("JFK");
        return ans;
    }

    public void DFS(String source){

        PriorityQueue<String> pq = graph.get(source);

        //might be that PQ of some node is not even initiallized therefore check for null
        //going to neighours
        while(pq != null && pq.size() > 0){
            String nbrs = pq.remove();
            DFS(nbrs);
        }

        //adding nodes while backtracking
        ans.addFirst(source);
    }
}

class Solution {
    public int regionsBySlashes(String[] grid) {
        /* Q31 graph  , DSU question
        1) convert n x n grid to n+1 x n+1 points on graph 
        2) convert 2d graph to 1d graph 
        3) connect boundaries and start answer with 1 as 1st region will be matrix itself
        4) figure out which type of slash connects which 2 points
        5) apply kruskal and check for cycle , if cycle exist increase region by 1
        */
        int n = grid.length;
        int dots = n+1;

        DSU temp = new DSU(dots * dots);

        //connecting boundaries point to 1 to form 1st region by matrix itself
        for(int i = 0 ;i < dots ; i++){
            for(int j = 0 ;j < dots ; j++){
                
                if(i == 0 || i == dots-1 || j==0 || j== dots-1){
                    //convert to cell no.
                    int cellno = i * dots + j;

                    // 0 and 0 will have same leader
                    temp.union(0 , cellno , DSU.parent , DSU.rank);
                }
                
            }
        }
        int ans = 1;

        //applying kruskal on grid
        for(int i = 0 ;i < grid.length ; i++){
            String str = grid[i];
            
            for(int j = 0 ;j < str.length(); j++){

                //(i+1 , j) && (i , j+1);
                if(str.charAt(j) == '/'){
                    int a = (i+1) * dots + j , b = i * dots + (j+1);

                    if(temp.union(a , b , temp.parent , temp.rank) == false)
                    ans++;
                }
                //(i , j) && (i+1 , j+1);
                else if(str.charAt(j) == '\\'){
                    int a = (i) * dots + j , b = (i+1) * dots + (j+1);

                    if(temp.union(a , b , temp.parent , temp.rank) == false)
                    ans++;

                    // j++;    //as its given for / we have '//' therefore we skip 1 char
                }
            }
        }
        return ans;

    }
    public static class DSU{
        static int parent[] , rank[];

        DSU(int n ){
            parent = new int[n];
            rank = new int[n];

            for(int i = 0 ;i < n ; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int child , int parent[]) {
            //if it is its own parent
            if(parent[child] == child){
                return parent[child];
            }

            int temp  = find(parent[child] , parent);    //optimization 1 (path compression)
            parent[child] = temp;

            return temp;
        }

        //x and y are childrens
        public boolean union(int x , int y , int parent[] , int rank[]){
            //finding leaders
            int lx = find(x , parent);
            int ly = find(y , parent);
            
            //combining based on ranks
            if(lx != ly){
                if(rank[lx] > rank[ly]){
                    parent[ly] = lx;
                }
                else if(rank[lx] < rank[ly]){
                    parent[lx] = ly;
                }

                else{
                    parent[lx] = ly;
                    rank[ly] ++ ;
                }
                return true;
            }
            return false;
        }
        
    }

}

class Solution{
	static int spanningTree(int V, int E, int edges[][]){
	    //already submitted through prims , now through kruskal
	    
	    int ans =0;
	    
	    Arrays.sort(edges , (a, b) -> a[2] - b[2]); //sort ascending order of weights
	    
	    DSU temp = new DSU(V);  //making DSU
	    
	    //taking sorted edges and processing them 1 by 1
	    for(int i = 0 ; i < edges.length ; i++){
	        int edge[] = edges[i];
	        int a = edge[0] , b = edge[1] , wt = edge[2];
	        
	        //if an edge already has a leader this will fail as that will make a cycle
	        if(temp.union(a , b , temp.parent , temp.rank)){
	            ans += edge[2];
	        }
	    }
	    return ans;
	    
	}
	//DSU template
	public static class DSU{
        int parent[] , rank[];

        DSU(int n ){
            parent = new int[n];
            rank = new int[n];

            for(int i = 0 ;i < n ; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public static int find(int child , int parent[]) {
            //if it is its own parent
            if(parent[child] == child){
                return parent[child];
            }

            int temp  = find(parent[child] , parent);    //optimization 1 (path compression)
            parent[child] = temp;

            return temp;
        }

        //x and y are childrens
        public static boolean union(int x , int y , int parent[] , int rank[]){
            //finding leaders
            int lx = find(x , parent);
            int ly = find(y , parent);
            
            //combining based on ranks
            if(lx != ly){
                if(rank[lx] > rank[ly]){
                    parent[ly] = lx;
                }
                else if(rank[lx] < rank[ly]){
                    parent[lx] = ly;
                }

                else{
                    parent[lx] = ly;
                    rank[ly] ++ ;
                }
                return true;
            }
            return false;
        }
        
    }

}

import java.util.Arrays;

public class Solution {
    public static int[] numOfIslandsII(int m, int n, int[][] q) {
        /* dynamic graph so we will use DSU , here set represent -> every cell which is part of
        same island will be under same set 
        */

        //making 2d array to 1d array based on cell no
        int parent[] = new int[m*n];
        int rank[] = new int[m*n];
        int ans[] = new int[q.length];

        Arrays.fill(parent, -1);

        //running queries one by one
        int count = 0;  //for islands

        for(int i = 0 ; i < q.length ; i++){
            int position[]= q[i];
            int x = position[0] , y = position[1];
            int cellno = x*n+y;

            //if already processed add to answer and continue
            if(parent[cellno] != -1){
                ans[i] = count;
                continue;
            }

            //if its coming first time make it island cell
            parent[cellno] = cellno;
            rank[cellno] = 1;
            count ++ ;          //new island
            
            //now check its adjacent cells if any one of it is island cell they will merge
            for(int dirs[] : dir){
                int rowdash = x + dirs[0];
                int coldash = y + dirs[1];
                int celldash = rowdash * n + coldash;

                //if invalid cell continue
                if(rowdash < 0 || coldash < 0 || rowdash >= m || coldash >= n 
                || parent[celldash] == -1)
                continue;
                
                //if valid cell combine both islands and decrease count 
                union(celldash , cellno , parent ,rank);
                count--;
                
            }
            
            ans[i] = count;
        }
        return ans;
    }

    public static int dir[][] = {{0,1} , {1,0} , {-1,0} , {0,-1}};
    public static int find(int x , int[] parent){
        if(parent[x] == x)
        return x;
        
        int temp = find(parent[x] , parent);
        parent[x] = temp;
        return temp;
    }
    public static void union(int x , int y , int[] parent , int[] rank){
        int lx = find(x , parent);
        int ly = find(y , parent);

        if(lx != ly){
            if(rank[lx] > ly){
                parent[ly] = lx;
            }
            else if(rank[lx] < ly){
                parent[lx] = ly;
            }
            else{
                parent[lx] = ly;
                rank[ly] ++;
            }
        }
    }
}

class Solution {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        /* as its kind of a dynamic graph we use DSU 
        */
        
        //giving common edges top priority that is of type 3
        Arrays.sort(edges , (a,b)-> b[0] - a[0]);
        
        //alice nodes=1 as for 1st merge 2 nodes get connected to each other
        int removed_edge = 0, alice_nodes = 1, bob_nodes = 1;

        DSU alice = new DSU(n+1);   //1 based indexing
        DSU bob = new DSU(n+1);

        for(int edge[] : edges){
            
            //taking out edges
            int a = edge[1] , b = edge[2];

            //giving common edges top priority
            if(edge[0] == 3){
                
                //if leaders of a and b are not same they will get merged 
                if(alice.union(a , b , alice.parent , alice.rank)){
                    bob.union(a , b , bob.parent , bob.rank);
                    alice_nodes++;
                    bob_nodes ++;
                }
                //if leaders are same that edge can be removed
                else
                removed_edge++;
                
            }
            else if(edge[0] == 2){
                if(bob.union(a , b , bob.parent , bob.rank))
                bob_nodes ++;
                
                else
                removed_edge++;
            }
            else{
                if(alice.union(a , b , alice.parent , alice.rank))
                alice_nodes ++;
                
                else
                removed_edge++;
            }
        }

        if(alice_nodes != n || bob_nodes != n)
        return -1;

        return removed_edge;
    }

    public class DSU{
        int parent[] , rank[];

        DSU(int n ){
            parent = new int[n];
            rank = new int[n];

            for(int i = 0 ;i < n ; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int child , int parent[]) {
            //if it is its own parent
            if(parent[child] == child){
                return parent[child];
            }

            int temp  = find(parent[child] , parent);    //optimization 1 (path compression)
            parent[child] = temp;

            return temp;
        }

        //x and y are childrens
        public boolean union(int x , int y , int parent[] , int rank[]){
            //finding leaders
            int lx = find(x , parent);
            int ly = find(y , parent);
            
            //combining based on ranks
            if(lx != ly){
                if(rank[lx] > rank[ly]){
                    parent[ly] = lx;
                }
                else if(rank[lx] < rank[ly]){
                    parent[lx] = ly;
                }

                else{
                    parent[lx] = ly;
                    rank[ly] ++ ;
                }
                return true;
            }
            return false;
        }
        
    }
}

class DSU {
    /* Q27 graph playlist , DSU template*/
    private int[] parent;
    private int[] rank;

    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    public boolean union(int x, int y) {
        int xset = find(x), yset = find(y);
        if (xset != yset) {
            if (rank[xset] < rank[yset]) {
                parent[xset] = yset;
            } else {
                parent[yset] = xset;
            }
            if (rank[xset] == rank[yset]) {
                rank[xset]++;
            }
            return true;
        }
        return false;
    }
}

class Solution {
    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        DSU dsu = new DSU(n);
        for (int i = 0; i < queries.length; i++) {
            queries[i] = new int[] { queries[i][0], queries[i][1], queries[i][2], i };
        }

        Arrays.sort(queries, (a, b) -> Integer.compare(a[2], b[2]));
        Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));

        int i = 0;
        boolean[] res = new boolean[queries.length];
        for (int[] q : queries) {
            while (i < edgeList.length && edgeList[i][2] < q[2]) {
                dsu.union(edgeList[i][0], edgeList[i][1]);
                i++;
            }

            if (dsu.find(q[0]) == dsu.find(q[1])) {
                res[q[3]] = true;
            }
        }

        return res;
    }
}

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        /*Q26  graph playlist ,bellman ford

            we are not using any temp array here as we dont need result of every iteration
            we just need minimum path from source to every dest and 

            we will return max of all min-paths as our answer
        */

        int path[] = new int[n];
        Arrays.fill(path , Integer.MAX_VALUE);
        path[k-1] = 0;  

        int ans = -1;
        for(int i = 0 ;i < n-1 ; i++){
            
            for(int time[] : times){
                int u = time[0] , v = time[1] , wt = time[2];

                if(path[u-1] == Integer.MAX_VALUE)
                continue;

                //turned into 0 based indexing
                path[v-1] = Math.min(path[v-1] ,path[u-1] + wt );

            }
        }

        //finding maximum of all min paths
        for(int i = 0 ;i < n ; i++)
        ans = Math.max(ans , path[i]);

        //if any min path is still max_Value we return -1
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        /* Q25 , bellman ford variation 
        -> We need to use another array temp so that the distances from the previous    
        iteration stored in dist don't change. 

        if we dont do that the array is going to dynamically change with each iteration of
        inside loop and we are not going to get ith edge answers .

        */

        //making path array 
        int[] path = new int[n];
        Arrays.fill(path , Integer.MAX_VALUE);
        path[src] = 0;  //cost of src from src = 0


        //firing bellman ford for K times so we just get <= k edges answer in the path
        for(int i = 0 ;i <= k ; i++){
            
            //copying path array so it doesn't get updated dynamically but stores one 
            // iteration result in the path array 
            int temp[] = Arrays.copyOf(path , n);
            for(int[] flight : flights) {
                int u = flight[0] , v = flight[1] , wt = flight[2];

                if(path[u] == Integer.MAX_VALUE)
                continue;

                temp[v] = Math.min(temp[v] , path[u] + wt);
            }
            path = temp;
        }

        //we didnt get any answer for <= k edges 
        return path[dst] == Integer.MAX_VALUE ? -1 : path[dst];
    }
}

//{ Driver Code Starts
import java.util.*;
import java.io.*;
import java.lang.*;

class DriverClass {
    public static void main(String args[]) throws IOException {

        BufferedReader read =
            new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(read.readLine());
        while (t-- > 0) {
            String str[] = read.readLine().trim().split(" ");
            int V = Integer.parseInt(str[0]);
            int E = Integer.parseInt(str[1]);

            ArrayList<ArrayList<Integer>> edges = new ArrayList<>();

            int i = 0;
            while (i++ < E) {
                String S[] = read.readLine().trim().split(" ");
                int u = Integer.parseInt(S[0]);
                int v = Integer.parseInt(S[1]);
                int w = Integer.parseInt(S[2]);
                ArrayList<Integer> t1 = new ArrayList<>();
                t1.add(u);
                t1.add(v);
                t1.add(w);
                edges.add(t1);
            }

            int S = Integer.parseInt(read.readLine());

            Solution ob = new Solution();

            int[] ptr = ob.bellman_ford(V, edges, S);

            for (i = 0; i < ptr.length; i++) System.out.print(ptr[i] + " ");
            System.out.println();
        }
    }
}
// } Driver Code Ends


// User function Template for Java

/*
*   edges: vector of vectors which represents the graph
*   S: source vertex to start traversing graph with
*   V: number of vertices
*/
class Solution {
    static int[] bellman_ford(int vtx, ArrayList<ArrayList<Integer>> edges, int S) {
        /* Q24 of graph playlist , bellman Ford algo 
        */
        
        //adding all the edges once in a arraylist (already done here)
        
        //iterating v-1 times
        int path[] = new int[vtx];
        Arrays.fill(path , Integer.MAX_VALUE);
        path[S] = 0;    //source to source is 0
        
        for(int i = 0 ;i < vtx-1 ; i++){
            
            //iterating over every edge
            for(int j = 0 ; j < edges.size() ; j++){
                //taking out edge
                int u = edges.get(j).get(0);
                int v = edges.get(j).get(1);
                int wt = edges.get(j).get(2);
                
                if(path[u] == Integer.MAX_VALUE){
                    continue;
                }
                
                if(path[u] + wt < path[v])
                path[v] = path[u] + wt;
            }
        }
        
        /* if negative weight cycle exists in the graph , path on one node will 
        update if we do another iteration of bellmanford (Vth iteration)
        */
        //iterating over every edge for Vth time to check for negative weight cycle
            for(int j = 0 ; j < edges.size() ; j++){
                //taking out edge
                int u = edges.get(j).get(0);
                int v = edges.get(j).get(1);
                int wt = edges.get(j).get(2);
                
                if(path[u] == Integer.MAX_VALUE){
                    continue;
                }
                
                //if true then that means , cycle exists
                if(path[u] + wt < path[v]){
                    return new int[]{-1};
                }
                
            }
            
        
         for(int i = 0 ;i < vtx; i++){
             if(path[i] == Integer.MAX_VALUE)
             path[i] = 100000000;
         }
        return path;
    }
}

import java.util.* ;
import java.io.*; 
public class Solution {

    public static int getMinimumCost(int cities, int roads, int[][] Connections) {
        /* Q23 graph playlist , we need to find MST using prims algo
         */
         
         //making graph
        ArrayList<ArrayList<pair>> graph = new ArrayList<>();
	    
	    for(int i = 0 ;i < cities ; i++)
	    graph.add(new ArrayList<>());
	    
	    for(int[] connections : Connections){
	        graph.get(connections[0]-1).add(new pair(connections[1]-1,connections[2]));
	        graph.get(connections[1]-1).add(new pair(connections[0]-1,connections[2]));
	    }
	    
        //Prims to find MST
	    PriorityQueue<pair> q = new PriorityQueue<>();
	    q.add(new pair(0 , 0));
	    
	    int ans = 0 , count = 0;
	    boolean visited[] = new boolean[cities];
	    while(q.size() > 0){
	        pair rem = q.poll();
	        
	        int v = rem.v ,wt = rem.wt;
	        if(visited[v] == true)
	        continue;
	        
	        visited[v] = true;
	       // System.out.print(v + " " + wt + "\n");
	        ans += wt;
	
	        for(pair edge : graph.get(v)){
	            if(visited[edge.v] == false){
	                q.add(new pair(edge.v , edge.wt));
	            }
	        }
	        count ++;
	    }
	    
	    return count == cities ? ans : -1;

    }

    public static class pair implements Comparable<pair>{
        int v , wt ;
	    
	    pair(int v , int wt){
	        this. v = v;
	        this.wt = wt;
	    }
	    
	    public int compareTo(pair o){
	        return this.wt - o.wt;
	    }
    }    
}

 class Solution {
    public int swimInWater(int[][] grid) {
        /* Q22 graph playlist , we apply a modified djikstra algo to find the smallest route
        as smallest route will depend on the maximum time cell of that route , we write 
        compareTo function according to maxvalue

        every pair in PQ stores maximum time cell in that route 
        */
        int m = grid.length , n = grid[0].length;

        Queue<pair> pq = new PriorityQueue<>();
        pq.add(new pair(0 , 0 , grid[0][0] , grid[0][0]));
        boolean visited[][] = new boolean[m][n];

        //applying djikstra according to Max time cell in a route
        while(pq.size() > 0){
            pair rem = pq.remove();
            int x = rem.x , y = rem.y , wt = rem.wt , max = rem.max;

            visited[x][y] = true;

            if(x == m-1 && y == n-1)
            return max;

            //calling for all edges
            for(int i = 0 ;i < 4 ;i++){
                int rowdash = x + dir[i][0];
                int coldash = y + dir[i][1];
                
                //checking if edge is valid
                if(rowdash >= 0 && rowdash < m &&
                coldash >= 0 && coldash < n && visited[rowdash][coldash] == false  ){
                    
                    //finding new max in the current route and updating the next time cell
                    int newMax = Math.max(max , grid[rowdash][coldash]);
                    pq.add(new pair(rowdash ,coldash , grid[rowdash][coldash],newMax));
                }
                
            }
        }
        return -1;
    }

    public int dir[][] = {{0,1} , {1,0} , {-1,0} , {0,-1}};

    public class pair implements Comparable<pair>{
        int x , y , wt , max;

        pair(){

        }
        pair(int x , int y , int wt , int max){
            this.x = x;
            this.y = y;
            this.wt = wt;
            this.max = max;     //current max-time in route
        }

        public int compareTo(pair o){
            return this.max - o.max;
        }
    }
}

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution {

    public static int supplyWater(int n, int k, int[] wells, int[][] pipes) {
        /* Q21 graph playlist , we add Node 0 , as dummy node which
        acts as our wells edge for each wedge and then we find 
        MST for the whole graph
        */
        
        //making graph of pipes
        ArrayList<ArrayList<pair>> graph = new ArrayList<>();
        
        //initializing AL
        for(int i = 0 ;i <= n ; i++)
        graph.add(new ArrayList<>());

        for(int pipe[] : pipes){
            
            graph.get(pipe[0]).add(new pair(pipe[1],pipe[2]));
            graph.get(pipe[1]).add(new pair(pipe[0],pipe[2]));
        }

        //now adding Wells edge in graph for each vertex
        for(int i = 0 ;i < n ; i++){
            graph.get(i+1).add(new pair(0 , wells[i]));
            graph.get(0).add(new pair(i+1 , wells[i]));
        }

        //now running prims algo for MST 
        PriorityQueue<pair> pq = new PriorityQueue<>();
        pq.add(new pair(0,0));
        boolean visited[] = new boolean[n + 1];

        int ans = 0;
        while(pq.size() > 0){
            pair rem = pq.remove();
            int vtx = rem.vtx , wt = rem.wt;

            if(visited[vtx] == true){
                continue;
            }
            

            ans += wt;
            visited[vtx] = true;

            //adding neighours
            for(pair nbrs : graph.get(vtx)){
                if(visited[nbrs.vtx] == false)
                pq.add(nbrs);
            }

        }
        return ans;
    }
    
    public static class pair implements Comparable<pair>{
        int vtx , wt;

        pair(){

        }
        pair(int vtx , int wt){
            this.vtx = vtx;
            this.wt = wt;
        }

        public int compareTo(pair o){
            return this.wt - o.wt;
        }
    }
}

//{ Driver Code Starts


import java.util.*;
import java.io.*;
import java.lang.*;

public class Main{
	static BufferedReader br;
	static PrintWriter ot;
    public static void main(String args[]) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		ot = new PrintWriter(System.out);
		int t = Integer.parseInt(br.readLine().trim());
		while(t-- > 0){
			String s[] = br.readLine().trim().split(" ");
			int V = Integer.parseInt(s[0]);
			int E = Integer.parseInt(s[1]);
			int edges[][] = new int[E][3];
			for(int i = 0; i < E; i++){
				s = br.readLine().trim().split(" ");
				edges[i][0] = Integer.parseInt(s[0]);
				edges[i][1] = Integer.parseInt(s[1]);
				edges[i][2] = Integer.parseInt(s[2]);
			}
			ot.println(new Solution().spanningTree(V, E, edges));
		}
		ot.close();
	}
}
// } Driver Code Ends


// User function Template for Java

class Solution{
	static int spanningTree(int V, int E, int edges[][]){
	    
	    ArrayList<ArrayList<pair>> graph = new ArrayList<>();
	    
	    for(int i = 0 ;i < V ; i++)
	    graph.add(new ArrayList<>());
	    
	    for(int[] edge : edges){
	        graph.get(edge[0]).add(new pair(edge[1],edge[2]));
	        graph.get(edge[1]).add(new pair(edge[0],edge[2]));
	    }
	    
	    PriorityQueue<pair> q = new PriorityQueue<>();
	    q.add(new pair(0 , 0));
	    
	    int ans = 0;
	    boolean visited[] = new boolean[V];
	    while(q.size() > 0){
	        pair rem = q.poll();
	        
	        int v = rem.v ,wt = rem.wt;
	        if(visited[v] == true)
	        continue;
	        
	        visited[v] = true;
	       // System.out.print(v + " " + wt + "\n");
	        ans += wt;
	
	        for(pair edge : graph.get(v)){
	            if(visited[edge.v] == false){
	                q.add(new pair(edge.v , edge.wt));
	            }
	        }
	        
	    }
	    
	    return ans;
	}
	
	public static class pair implements Comparable<pair>{
	    int v , wt ;
	    
	    pair(int v , int wt){
	        this. v = v;
	        this.wt = wt;
	    }
	    
	    public int compareTo(pair o){
	        return this.wt - o.wt;
	    }
	}
}

//{ Driver Code Starts
/*package whatever //do not write package name here */

import java.io.*;
import java.util.*;
import java.math.*;

class GFG {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = Integer.parseInt(sc.next());
		while(t-- > 0)
		{
		    int n = Integer.parseInt(sc.next());
		    int k = Integer.parseInt(sc.next());
		    
		    String[] words = new String[n];
		    
		    for(int i=0;i<n;i++)
		    {
		        words[i] = sc.next();
		    }
		    
		    Solution ob = new Solution();
		  //  System.out.println(T.findOrder(words,k));
		    String order = ob.findOrder(words,n,k);
		    if(order.length() == 0){
		        System.out.println(0);
		        continue;
		    }
		    String temp[] = new String[n];
		    for(int i=0;i<n;i++)
		        temp[i] = words[i];
		    
		    Arrays.sort(temp, new Comparator<String>(){
		    
		      @Override
                public int compare(String a, String b) {
                    int index1 = 0;
                    int index2 = 0;
                    for(int i = 0; i < Math.min(a.length(), b.length()) 
                                        && index1 == index2; i++) {
                        index1 = order.indexOf(a.charAt(i));
                        index2 = order.indexOf(b.charAt(i));
                    }
                
                    if(index1 == index2 && a.length() != b.length()) 
                    {
                        if(a.length() < b.length())
                            return -1;
                        else
                            return 1;
                    }
                
                    if(index1 < index2)
                        return -1;
                    else
                        return 1;
                        
                }
		    });
		    
		    int flag = 1;
		    for(int i=0;i<n;i++)
		    {
		        if(!words[i].equals(temp[i]))
	            {
	                flag = 0;
	                break;
	            }
		    }
		    
		    System.out.println(flag);
		}
	}
	
}

// } Driver Code Ends


//User function Template for Java

class Solution
{
    public String findOrder(String [] dict, int n, int k)
    {//doesn't work on GFG , take a look once
        HashMap<Character , HashSet<Character>> graph = new HashMap<>();
        HashMap<Character,Integer> indegree = new HashMap<>();

        for(String word : dict){
            for(char ch : word.toCharArray())
            indegree.put(ch , 0);
        }
        //making graph between letters
        for(int i = 1 ; i < dict.length ; i++){
            String word1 = dict[i-1] , word2 = dict[i];
            
            int len = Math.min(word1.length() , word2.length());
            // System.out.println(word1 +" " + word2);
            for(int j = 0 ; j < len ; j++){
                char ch1 = word1.charAt(j) , ch2 = word2.charAt(j);
                
                // System.out.println(ch1 +" " + ch2);
                if(ch1 != ch2){
                    //making edge between ch1 and ch2
                    HashSet<Character> temp = graph.getOrDefault(ch1 , new HashSet<>());
                    temp.add(ch2);
                    graph.put(ch1 , temp);
                    
                    //increasing indegree of ch2 , and puttin indegree of ch1 = 0
                    indegree.put(ch2 , indegree.getOrDefault(ch2,0)+1);
                    
                    if(indegree.containsKey(ch1) == false)
                    indegree.put(ch1 , 0);
                    
                    break;
                }
            }
            
            //calling kahn's algo
        }
        
        return kahn(graph , indegree);
    }
    
    public String kahn(HashMap<Character , HashSet<Character>> graph,
    HashMap<Character,Integer> indegree){
        
        StringBuilder sb = new StringBuilder();
        
        LinkedList<Character> q = new LinkedList<>();
        
        //adding all nodes with indegree 0 
        for(char ch : indegree.keySet()){
            if(indegree.get(ch) == 0)
            q.addLast(ch);
        }
        //firing kahn
        
        while(q.size()>0){
            char ch = q.removeFirst();
            sb.append(ch+"");
            
            //reducing indegree of its neighours
            if(graph.containsKey(ch)){
                    for(char nbr : graph.get(ch)){
                    indegree.put(nbr , indegree.get(nbr)-1);
                    
                    //if indegree becomes 0 remove it and add to q
                    if(indegree.get(nbr) == 0){
                        indegree.remove(nbr);
                        q.addLast(nbr);
                    }
                    
                }
            }
        }
        
        return sb.toString();
    }
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        /* Q18 of graph playlist , we will do this through kahn's  algo or topological sort
        assume the problem to be a graph where ever node has a dependency/prequisite to 
        another node also known as indegree.
        */

        //taking input 
        int n = numCourses;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        //initializing arraylist
        for(int i = 0 ; i < n ; i++)
        graph.add(new ArrayList<>());

        //making graph
        for(int pre[] : prerequisites)
        graph.get(pre[1]).add(pre[0]); 
        
        //calling kahn's  algo 
        ArrayList<Integer> ans = kahn(n , graph);

        //if all vertix are covered in kahn's algo return true , else false
        if(ans.size() == n )
        return true;

        return false;

    }

    public ArrayList<Integer> kahn(int n , ArrayList<ArrayList<Integer>> graph){
        ArrayList<Integer> ans = new ArrayList<>(); //can also count instead arraylist

        //finding indegree
        int[] indegree = new int[n];

        for(int i = 0 ;i < n ; i++){
            for(int nbr : graph.get(i))
            indegree[nbr] ++;
        }

        //making a q and adding all nodes with indegree 0
        LinkedList<Integer> q = new LinkedList<>();

        for(int i = 0 ; i < n ;i++){
            if(indegree[i] == 0)
            q.addLast(i);
        }

        //now running kahn's algo
        while(q.size()>0){
            int rem = q.removeFirst();
            ans.add(rem);                   //storing in topological order

            //decreasing indegree/dependency of neighours
            for(int nbr : graph.get(rem)){
                indegree[nbr] --;

                //if node's indegree becomes 0 we add it to the q
                if(indegree[nbr] == 0)
                q.addLast(nbr);
            }
        }

        return ans;
    }
}

//{ Driver Code Starts
import java.io.*;
import java.util.*;


class IntArray
{
    public static int[] input(BufferedReader br, int n) throws IOException
    {
        String[] s = br.readLine().trim().split(" ");
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = Integer.parseInt(s[i]);
        
        return a;
    }
    
    public static void print(int[] a)
    {
        for(int e : a)
            System.out.print(e + " ");
        System.out.println();
    }
    
    public static void print(ArrayList<Integer> a)
    {
        for(int e : a)
            System.out.print(e + " ");
        System.out.println();
    }
}


class IntMatrix
{
    public static int[][] input(BufferedReader br, int n, int m) throws IOException
    {
        int[][] mat = new int[n][];
        
        for(int i = 0; i < n; i++)
        {
            String[] s = br.readLine().trim().split(" ");
            mat[i] = new int[s.length];
            for(int j = 0; j < s.length; j++)
                mat[i][j] = Integer.parseInt(s[j]);
        }
        
        return mat;
    }
    
    public static void print(int[][] m)
    {
        for(var a : m)
        {
            for(int e : a)
                System.out.print(e + " ");
            System.out.println();
        }
    }
    
    public static void print(ArrayList<ArrayList<Integer>> m)
    {
        for(var a : m)
        {
            for(int e : a)
                System.out.print(e + " ");
            System.out.println();
        }
    }
}

class GFG {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            
            int[] a = new int[2];
            String s[] = br.readLine().trim().split(" ");
            if(s.length == 2){
                a[0] = Integer.parseInt(s[0]);
                a[1] = Integer.parseInt(s[1]);
            } else{
                a[0] = Integer.parseInt(s[0]);
                s = br.readLine().trim().split(" ");
                a[1] = Integer.parseInt(s[0]);
            }
            int[][] edges = IntMatrix.input(br, a[1], 2);
            
            
            int src; 
            src = Integer.parseInt(br.readLine());
            
            
            int dst; 
            dst = Integer.parseInt(br.readLine());
            
            Solution obj = new Solution();
            int res = obj.minimumEdgeReversal(edges, a[0], a[1], src, dst);
            
            System.out.println(res);
            
        }
    }
}

// } Driver Code Ends


class Solution {
    public static int minimumEdgeReversal(int[][] edges, int n, int m, int src, int dst) {
        //taking input
        ArrayList<ArrayList<pair>> graph = new ArrayList<>();
        for(int i = 0 ;i < n ; i++)
        graph.add(new ArrayList<>());
        
        for(int edge[] : edges){
            //making into 0 based indexing
            graph.get(edge[0]-1).add(new pair(edge[1]-1,0));
            graph.get(edge[1]-1).add(new pair(edge[0]-1,1));
        }
        
        boolean visited[] = new boolean[n];
        
        /* now using 0-1 bfs , we just replaec PQ with linkedlist and make 2 partion
        as there are just 2 weights in the graph , +0 edges are added in the
        front and +1 are added in the end , makes complexity O(E+V)
        */
        LinkedList<pair> q = new LinkedList<>();
        q.addLast(new pair(src-1 , 0));
        
        while(q.size() > 0){
            pair rem = q.removeFirst();
            int vtx = rem.vtx , wt = rem.wt;
            
            visited[vtx] = true;
            
            if(vtx == dst-1)
            return wt;
            
            for(pair edge : graph.get(vtx)){
                
                if(visited[edge.vtx] == false){
                    if(edge.wt == 0)
                    q.addFirst(new pair(edge.vtx , wt + 0));
                    
                    else
                    q.addLast(new pair(edge.vtx , wt + 1));
                }
            }
            
        }
        return - 1;
    }
    
    public static class pair implements Comparable<pair>{
        int vtx , wt; 
        
        pair(int vtx , int wt){
            this.vtx = vtx;
            this.wt = wt;
        }
        
        public int compareTo(pair o){
            return this.wt - o.wt;
        }
    }
}
        

//{ Driver Code Starts
import java.io.*;
import java.util.*;


class IntArray
{
    public static int[] input(BufferedReader br, int n) throws IOException
    {
        String[] s = br.readLine().trim().split(" ");
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = Integer.parseInt(s[i]);
        
        return a;
    }
    
    public static void print(int[] a)
    {
        for(int e : a)
            System.out.print(e + " ");
        System.out.println();
    }
    
    public static void print(ArrayList<Integer> a)
    {
        for(int e : a)
            System.out.print(e + " ");
        System.out.println();
    }
}


class IntMatrix
{
    public static int[][] input(BufferedReader br, int n, int m) throws IOException
    {
        int[][] mat = new int[n][];
        
        for(int i = 0; i < n; i++)
        {
            String[] s = br.readLine().trim().split(" ");
            mat[i] = new int[s.length];
            for(int j = 0; j < s.length; j++)
                mat[i][j] = Integer.parseInt(s[j]);
        }
        
        return mat;
    }
    
    public static void print(int[][] m)
    {
        for(var a : m)
        {
            for(int e : a)
                System.out.print(e + " ");
            System.out.println();
        }
    }
    
    public static void print(ArrayList<ArrayList<Integer>> m)
    {
        for(var a : m)
        {
            for(int e : a)
                System.out.print(e + " ");
            System.out.println();
        }
    }
}

class GFG {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            
            int[] a = new int[2];
            String s[] = br.readLine().trim().split(" ");
            if(s.length == 2){
                a[0] = Integer.parseInt(s[0]);
                a[1] = Integer.parseInt(s[1]);
            } else{
                a[0] = Integer.parseInt(s[0]);
                s = br.readLine().trim().split(" ");
                a[1] = Integer.parseInt(s[0]);
            }
            int[][] edges = IntMatrix.input(br, a[1], 2);
            
            
            int src; 
            src = Integer.parseInt(br.readLine());
            
            
            int dst; 
            dst = Integer.parseInt(br.readLine());
            
            Solution obj = new Solution();
            int res = obj.minimumEdgeReversal(edges, a[0], a[1], src, dst);
            
            System.out.println(res);
            
        }
    }
}

// } Driver Code Ends


class Solution {
    public static int minimumEdgeReversal(int[][] edges, int n, int m, int src, int dst) {
        //taking input
        ArrayList<ArrayList<pair>> graph = new ArrayList<>();
        for(int i = 0 ;i < n ; i++)
        graph.add(new ArrayList<>());
        
        for(int edge[] : edges){
            //making into 0 based indexing
            graph.get(edge[0]-1).add(new pair(edge[1]-1,0));
            graph.get(edge[1]-1).add(new pair(edge[0]-1,1));
        }
        
        boolean visited[] = new boolean[n];
        //making priority queue for djikstra
        PriorityQueue<pair> q = new PriorityQueue<>();
        q.add(new pair(src-1,0));
        
        //djikstra
        while(q.size()>0){
            pair rem = q.poll();
            int vtx = rem.vtx , wt = rem.wt;
            
            visited[vtx] = true;
            
            if(vtx == dst-1)
            return wt;
            
            for(pair nbr: graph.get(vtx)){
                
                if(visited[nbr.vtx] == false){
                    
                    q.add(new pair(nbr.vtx , nbr.wt + wt));
                }
            }
            
        }
        return -1;
    }
    
    public static class pair implements Comparable<pair>{
        int vtx , wt; 
        
        pair(int vtx , int wt){
            this.vtx = vtx;
            this.wt = wt;
        }
        
        public int compareTo(pair o){
            return this.wt - o.wt;
        }
    }
}
        

class Solution {
    public int slidingPuzzle(int[][] board) {
        /* Q9 of graph playlist , we make a allowed swaps for every index and call bfs
            for intial string and whenever initial string is equal to target string we return
            that level
        */

        //making a hashset of visited strings
        HashSet<String> set = new HashSet<>();

        String target = "123450";
        
        //making initial string
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ;i < board.length ; i++){
            for(int j = 0 ; j < board[0].length ; j++){
                sb.append(board[i][j]);
            }
        }
        String initial = sb.toString();

        //making a q and adding initial to the q
        LinkedList<String> q= new LinkedList<>();
        q.addLast(initial);

        //make 2d array for allowed swaps for every index
        int [][] swaps = {{1,3} , {0,4 ,2}, {1,5} , {0,4}, {1 ,3 ,5} , {2 , 4}};

        //applying bfs and returning level
        int level = 0;

        while(q.size() > 0){
            int size = q.size();
            while(size-- > 0){
                String rem = q.pop();
                
                // System.out.println(target + "->" + rem);
                if(rem.equals(target))
                return level;

                //find 0th index in current string
                int idx = rem.indexOf('0');

                // System.out.println(idx);
                //applying swaps 
                for(int swap : swaps[idx]){
                    String swapped = swap(idx , swap , rem);
                    // System.out.println(swapped);

                    if(set.contains(swapped) == false){
                        set.add(swapped);
                        q.add(swapped);
                    }
                    
                }
            }
            level++;
        }
        return -1;
    }

    public String swap (int i , int j , String str){
        StringBuilder sb = new StringBuilder(str);

        sb.setCharAt(i , str.charAt(j));
        sb.setCharAt(j , str.charAt(i));

        return sb.toString();
    }
}

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
       /* Q8 graph playlist , make a hashmap of busstops - busses , busvisited , 
       busStop visited . first add all busStops -> busses in hashmap 
       
       add source bus to q and fire bfs with a level variable in 2 while loops
       
       take out bus from busstops in HM and add all busStops which can be reached from that
       busStop , as they can all reach with 1 bus only , mark bus and bus stop visited and 
       increase level 

       return level when target busStop is reachedd
       */

       //making a HM of busstops -> busno.
       HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();

       //adding bustops -> busno.
       for(int i =0 ; i< routes.length ; i++){
           for(int j = 0 ; j < routes[i].length ; j++){
               ArrayList<Integer> temp = map.getOrDefault(routes[i][j] , new ArrayList<>());
               temp.add(i);
               map.put(routes[i][j] , temp);
           }
       }

       LinkedList<Integer> q = new LinkedList<>();
       HashSet<Integer> busVisited = new HashSet<>();
       HashSet<Integer> busStopVisited = new HashSet<>();
       int level = 0;

        //adding source busStop to Q
        q.addLast(source);

        while(q.size() > 0){
            int size = q.size();

            while(size-- > 0){
                //getting busses corresponding to bus stop
                int rem = q.pop();
                if(rem == target)
                return level;

                ArrayList<Integer> busses = map.get(rem);

                //looping over all the busses which can be taken from the current busStop
                for(int bus : busses){
                    
                    //only if the bus is not visited
                    if(busVisited.contains(bus) == false){
                        int [] busStops = routes[bus];
                        
                        //getting busStops which can be reached for current bus
                        for(int busStoops : busStops){
                            
                            //only if the busStop is not visited
                            if(busStopVisited.contains(busStoops) == false){
                                q.addLast(busStoops);
                                busStopVisited.add(busStoops);  //marking visited
                            }
                        }
                        busVisited.add(bus);    //marking visited
                    }
                }
                
            }
            level++;
        }

        return - 1;
       
    }
}

class Solution {
    public int shortestBridge(int[][] grid) {
        int m = grid.length , n = grid[0].length ;
        LinkedList<int[]> q = new LinkedList<>();
        boolean flag = false;
        boolean [][] visited = new boolean[m][n];

        for(int i = 0 ;i < m ;i++){
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j] == 1){
                    dfs(grid , i , j , m , n ,visited , q);
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }

        int distance = 0;
        //firing bfs
        while(q.size()>0){
            int size = q.size();
            while(size-- > 0){
                int[] rem = q.pop();
            
                for(int i = 0 ;i < 4 ; i++){
                    int rowdash = rem[0] + dir[i][0];
                    int coldash = rem[1] + dir[i][1];

                    if(rowdash >= 0 && coldash >=0 && rowdash < m && coldash < n && 
                    visited[rowdash][coldash] == false ){
                        if(grid[rowdash][coldash] == 1)
                        return distance;
                        q.addLast(new int[]{rowdash,coldash});
                        visited[rowdash][coldash] = true;
                    }
                    
                }
            }
            distance ++ ;
        }
        return -1;
    }

    public void dfs(int[][] grid , int row , int col , int m , int n ,boolean[][] visited ,
    LinkedList<int[]> q){
        if(row < 0 || col < 0 || row >= m || col >= n || visited[row][col] == true || 
        grid[row][col] == 0)
        return;

        visited[row][col] = true;
        q.addLast(new int[]{row,col});

        for(int i = 0 ;i < 4 ; i++){
            dfs(grid , row + dir[i][0] ,col + dir[i][1] , m , n ,visited , q);
        }
    }

    public int dir [][] = {{0,1},{1,0},{-1,0},{0,-1}};

    // public class pair{
    //     int x , y , dist;

    //     pair(int x , int y , int dist){
    //         this.x = x; this.y = y ; this.dist = dist;
    //     }
    // }
}

class Solution {
    public int shortestBridge(int[][] grid) {
        /* Q7 of graph playlist , we know there are just 2 islands , therefore we will first
        
        we will traverse the array and fire dfs from the first 1 we encounter to store that 
        island in the queue , then break out of the loop

        now that we have 1 island we will fire BFS , from all 1s of this island which is 
        stored in the queue to find the nearest 1 of 2nd island , the first 1 we encounter
        we will return level of that 1 as that will be no. of 0s to be flipped
        */

        int m = grid.length , n = grid[0].length ;
        LinkedList<pair> q = new LinkedList<>();
        boolean flag = false;
        boolean [][] visited = new boolean[m][n];

        //finding first 1
        for(int i = 0 ;i < m ;i++){
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j] == 1){
                    //firing dfs to find 1st island and store all 1s in Q
                    dfs(grid , i , j , m , n ,visited , q);
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }

        //firing bfs
        while(q.size()>0){
            pair rem = q.pop();
            int row = rem.x ; int col = rem.y ; int dist = rem.dist;

            for(int i = 0 ;i < 4 ; i++){
                int rowdash = row + dir[i][0];
                int coldash = col + dir[i][1];

                //if valid cell , make it true and add to q
                if(rowdash >=0 && coldash >=0 && rowdash < m && coldash < n && 
                visited[rowdash][coldash] == false ){
                    if(grid[rowdash][coldash] == 1)
                    return dist;    

                    visited[rowdash][coldash] = true;
                    q.addLast(new pair(rowdash ,coldash , dist + 1));
                }
                
            }
            
        }
        return -1;
    }

    public void dfs(int[][] grid , int row , int col , int m , int n ,boolean[][] visited ,
    LinkedList<pair> q){
        if(row < 0 || col < 0 || row >= m || col >= n || visited[row][col] == true || 
        grid[row][col] == 0)
        return;

        //marking the element true and adding it to the q
        visited[row][col] = true;
        q.addLast(new pair(row , col , 0));

        for(int i = 0 ;i < 4 ; i++){
            dfs(grid , row + dir[i][0] ,col + dir[i][1] , m , n ,visited , q);
        }
    }

    //direction array
    public int dir [][] = {{0,1},{1,0},{-1,0},{0,-1}};

    //pair class for row , col and distance
    public class pair{
        int x , y , dist;

        pair(int x , int y , int dist){
            this.x = x; this.y = y ; this.dist = dist;
        }
    }
}

class Solution {
    public int maxDistance(int[][] grid) {
        /* Q-6 of graph playlist , we make a pair class with row , col , distance  , first 
        add all 1s to the q with distance 0 , fire bfs , encountering a 0 we change it to 1
        and make its distance + 1 
        
        we keep a max variable also while we fire bfs and store max distance along the way
        
        */
        int m = grid.length , n = grid[0].length ;
        LinkedList<pair> q = new LinkedList<>();
        
        //adding all 1s to q
        int water = 0 , land = 0;
        for(int i = 0 ;i < m ;i++){
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j] == 1){
                    land ++;
                    q.addLast(new pair(i, j , 0));
                }
                

                else
                water++;
            }
        }
        
        //edge case
        if(water == 0 || land == 0)  return -1;

    
        int max = -1;
        //firing bfs
        while(q.size() > 0){
            pair rem = q.removeFirst();
            int row = rem.x ; int col = rem.y ; int dist = rem.dist;

            max = Math.max(dist , max);

            for(int i =0 ;i < 4 ; i++){
                int rowdash = row + dir[i][0];
                int coldash = col + dir[i][1];

                //if valid water cell change it to land cell and make its dist + 1
                if(rowdash >=0 && coldash >=0 && rowdash < m && coldash < n &&
                grid[rowdash][coldash] == 0){
                    grid[rowdash][coldash] = 1;
                    q.add(new pair(rowdash , coldash , dist + 1));
                }
            }
        }

        return max;
    }

    public int dir [][] = {{0,1},{1,0},{-1,0},{0,-1}};

    public class pair{
        int x , y , dist;

        pair(int x , int y , int dist){
            this.x = x; this.y = y ; this.dist = dist;
        }
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        /* Q5 of graph playlist , we make a pair class with row , col , time , we add all 
        2's in the q and fire bfs , and increase the time of the next oranges as that 
        will be the time it takes for them to become rotten and then we also add those 
        oranges in the queue
        */
        LinkedList<pair> q = new LinkedList<>();
        int m = grid.length , n = grid[0].length;

        //counting fresh oranges and adding rottens to queue
        int fresh = 0 ;
        for(int i = 0 ;i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                if(grid[i][j] == 2)
                q.addLast(new pair(i , j , 0));
                
                else if(grid[i][j] == 1)
                fresh ++;
                
            }
        }

        int time = 0;
        //firing bfs
        while(q.size() > 0){
            pair rem = q.removeFirst();
            time = rem.time;
            int row = rem.x ;
            int col = rem.y;

            //adding next rotten oranges and updating their time
            for(int i = 0 ;i < 4 ; i++){
                int rowdash = row + dir[i][0];
                int coldash = col + dir[i][1];

                if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n &&
                grid[rowdash][coldash] == 1){
                    grid[rowdash][coldash] = 2;
                    fresh --;
                    q.addLast(new pair(rowdash,coldash , time + 1));
                }
            }
        }
        
        System.out.println(time);
        return fresh == 0 ? time : -1;
    }

    //directions and pair class with row , col , time
    public int[][] dir = {{0,1} , {1,0} , {-1,0} , {0,-1}};
    public class pair{
        int x , y , time;

        pair(int x , int y ,int time){
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
}

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        /* Q4 of graph playlist , add all zeroes to q and mark all 1 to -1 , fire bfs from 
        all zeroes to find nearest 1 and update distance of 1 
        */
        int m = mat.length , n = mat[0].length;

        LinkedList<pair> q = new LinkedList<>();

        //adding all zeroes to the q
        for(int i =0 ; i < m ; i++){
            for(int j = 0 ; j < n ;j++){
                if(mat[i][j] == 0)
                q.addLast(new pair(i , j));

                else
                mat[i][j] = -1; //marking the cell as unvisited
            }
        }

        //firing reverse bfs from zeroes to solve all 1's
        while(q.size()>0){
            pair rem = q.removeFirst();

            for(int i = 0 ;i < 4 ; i++){
                int rowdash = rem.x + dir[i][0];
                int coldash = rem.y + dir[i][1];

                //if valid cell
                if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n &&
                mat[rowdash][coldash] < 0){

                    //updating distance of the cell
                    mat[rowdash][coldash] = mat[rem.x][rem.y] + 1;
                    //adding it to q to solve further cells
                    q.addLast(new pair(rowdash , coldash));
                }
                
            }
        }

        return mat;

    }
    public int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};
    public class pair {
        int x , y;
        
        pair(int x , int y){
            this.x = x;
            this.y = y;
        }
    }
}

//{ Driver Code Starts
// Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;

// Position this line where user code will be pasted.

class GFG {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] grid = new int[n][m];

            for (int i = 0; i < n; i++) {

                for (int j = 0; j < m; j++) {
                    grid[i][j] = sc.nextInt();
                }
            }

            Solution ob = new Solution();
            int ans = ob.countDistinctIslands(grid);
            System.out.println(ans);
        }
    }
}
// } Driver Code Ends


// User function Template for Java

class Solution {

    int countDistinctIslands(int[][] grid) {
        /*Q3 of graph playlist , we will find GCC and store the structure in form
        of string in a hashmap , if the same structure appears it wont be added in
        the hashmap 
        -> we will also add a character in string when backtracking (*edge case*) 
        -> we will return length of hashmap in the end
        */
        int m = grid.length , n = grid[0].length ;
    
        HashSet<String> set = new HashSet<>();
        for(int i =0 ;i < m ; i++){
            for(int j = 0 ;j < n ;j++){
                
                if(grid[i][j] == 1){
                    psf = new StringBuilder();
                    psf.append("x");
                    dfs(grid , i , j , m, n);
                    // System.out.println(psf);
                    set.add(psf.toString());
                }
                
            }
        }
        return set.size();
    }
    // up right down left
    public StringBuilder psf = new StringBuilder(); //path so far = structure
    public void dfs(int[][] grid , int row , int col , int m , int n ){
        //we need to make proactive call as we have to handle for psf
        
        grid[row][col] = 0; //marking 
        if(row-1 >= 0 && grid[row-1][col] == 1){
            psf.append("u");
            dfs(grid , row-1 , col , m , n);
        }
        
        if(col+1 < n && grid[row][col+1] == 1){
            psf.append("r");
            dfs(grid , row , col+1 , m , n);
        }
        
        if(row+1 < m && grid[row+1][col] == 1){
            psf.append("d");
            dfs(grid , row+1 , col , m , n);
        }
        
        if(col-1 >= 0 && grid[row][col-1] == 1){
            psf.append("l");
            dfs(grid , row , col-1 , m , n);
        }
        
        //adding backtracking character
        psf.append("z");
    }
}

class Solution {
    public int numEnclaves(int[][] grid) {
        /* Q2 of graph playlist , we fire GCC from boundary elements and make all 1's in those
        components as 0 , then we count left no. of 1's in the grid as those are the land cell
        which will not lead to boundary
        */
        
        //firing DFS to find components from boundary elements and making them 0
        int m = grid.length , n = grid[0].length;

        for(int i = 0 ;i < m ; i++){
            for(int j = 0 ; j< n ; j++){
                if(i == 0 || i == m-1 || j == 0 || j == n-1){
                    if(grid[i][j] == 1)
                    dfs(grid , i , j , m , n);
                }
            }
        }

        // count no. of land cells and return them
        int count = 0;
        for(int i = 0 ;i < m ; i++){
            for(int j = 0 ; j< n ; j++){
                    if(grid[i][j] == 1)
                    count++;
            }
        }
        return count;
    }

    int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
    public void dfs (int[][] grid , int row , int col , int m , int n){
        //base case
        if(row < 0 || col < 0 || row >= m || col >= n || grid[row][col] == 0)
        return;
        
        //making component's 1 to 0
        grid[row][col] = 0;
        
        for(int i =0 ;i < 4 ; i++)
        dfs(grid , row + dir[i][0] , col + dir[i][1] , m ,n);
    }
}

class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        /*Q-1 of graph playlist , we will fire DFS to find component and 
        also pass a count(which will keep track of same color neighours) , we will make the
        element visited by making its value negative 

        while backtracking we will change elements to positive which have count == 4 as those 
        will not be colored as they are not on the boundary
         */

        //taking out current color for component and firing DFS
        int comp = grid[row][col];
        int m = grid.length , n = grid[0].length;
        
        DFS(grid , row , col , comp , m , n);

        //changing negative elements to color
        for(int i = 0 ;i < m;i++){
            for(int j = 0 ; j < n ; j++){
                if(grid[i][j] < 0)
                grid[i][j] = color;
            }
        }
        return grid;
    }

    //direction variable for making calls
    public int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};

    public void DFS(int[][] grid, int row, int col, int comp , int m , int n ){
        
        grid[row][col] = -comp; //marking visited 
        int count = 0 ; 
        for(int i =0 ; i < 4;i++){
            int rowdash = row + dir[i][0];
            int coldash = col + dir[i][1];
            
            //base condition if neighour is not valid
            if(rowdash < 0 || coldash < 0 || rowdash >= m || coldash >= n ||
            Math.abs(grid[rowdash][coldash]) != comp)
            continue;
            
            //if neighour is valid count++
            count ++; 

            //if neighour is not visited call it
            if(grid[rowdash][coldash] > 0 )
            DFS(grid , rowdash , coldash , comp , m , n);
        }
        //while backtracking checking if its a boundary element
        //if all neighours are equal to comp its not a boundary element
        if(count == 4)
        grid[row][col] = comp;
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        
        int m = grid.length;
        int n = grid[0].length;

        int dp[][] = new int [m][n];

        //if robot is on the 0,0 return 0
        if(grid[0][0] == 1) return 0;

        //traversing first row and coloumn 
        for(int j = 0 ; j < n ; j++){
            
            if(grid[0][j] == 1){ //that is a obstacle exist in this row
                dp[0][j] = 0;
                break;
            }

            else
            dp[0][j] = 1;         //one way to reach that cell
            
        }

        for(int i = 0 ; i < m ; i++){
            
            if(grid[i][0] == 1){    //that is a obstacle exist in first coloumn
                dp[i][0] = 0;
                break;
            }

            else
            dp[i][0] = 1; 
        }

        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }

        //now traversing rest of the grid

        for(int i = 1 ; i < m ; i++){
            for(int j = 1 ; j < n ; j++){

                if(grid[i][j] == 1)
                dp[i][j] = 0;         //no way of reaching if its an obstacle

                else
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        
            
        
        return dp[m-1][n-1];

    }
}

class Solution {
    public int uniquePathsIII(int[][] grid) {
        /* 
        basically this is a question of hamiltonian path in graphs
        
        find position of 1 and send it to dfs function if there exists a path with 
        only one visit per node we will increase the count
        */
        int m  = grid.length  , n = grid[0].length;

        //finding position of 1 and count no. of -1 
        int pos_x = 0  , pos_y = 0; //finding position of 1
        
        int count = 0;        //calculating no. of -1

        HashSet<String> visited = new HashSet<>();
        
        for(int i = 0 ; i< m ; i++){
            for(int j = 0 ; j < n ;j++){

                if(grid[i][j] == 1){
                    pos_x = i ;
                    pos_y = j ;
                }

                else if(grid[i][j] == -1)
                count ++;
            }
        }
        //finding total no.of tiles without -1 
        count = m*n - count -1 ;
        dfs(grid , pos_x , pos_y , visited , count);

        return paths;
    }

    public int paths = 0;

    public void dfs(int[][] grid , int i , int j , HashSet<String> visited , int count){
        //base case
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length ||
        visited.contains(i + "*" + j) || grid[i][j] == -1)
        return ;

        //when at destination , check if all the vertices are covered
        if(grid[i][j] == 2){
            
            System.out.println(visited.size() + "->" + count);
            
            if(visited.size() == count)
            paths++;

            return;
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(i + "*" + j);
        
        visited.add(sb.toString());
        
        //calls for 4 directions
        dfs(grid , i , j+1 , visited , count);
        dfs(grid , i , j-1 , visited , count);
        dfs(grid , i+1 , j , visited , count);
        dfs(grid , i-1 , j , visited , count);
        
        visited.remove(sb.toString());

    }
}

class Solution {
    public int findCircleNum(int[][] isConnected) {
        /* convert this question to graph components */

        //making graph using input
        HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();
        int n = isConnected.length;   //nxn matrix

        for(int i = 0 ; i < n ;i++){
            for(int j = 0 ; j < n ; j++){
                
                //storing edges between nodes
                if(isConnected[i][j] == 1){
                    graph.computeIfAbsent(i , k -> new ArrayList<>()).add(j);
                    graph.computeIfAbsent(j , k -> new ArrayList<>()).add(i);
                }
            }
        }

        boolean visited[] = new boolean[n];
        int component = 0;
        //looping through every node and firing dfs
        for(int i = 0 ; i < n ; i++){

            if(visited[i] == false){
                
                dfs(graph , i , visited);
                component++;
            }
        }

        return component;
    }

    public void dfs (HashMap<Integer,ArrayList<Integer>> graph , int source ,
    boolean[] visited){

        visited[source] = true;

        for(int edge : graph.get(source)){
            if(visited[edge] == false)
            dfs(graph , edge , visited);
        }
    }












}

class Solution {
    public int numIslands(char[][] grid) {
        /* we treat this like a question of graph to find components which are 
        islands in this case 
        */
        boolean visited[][] = new boolean [grid.length][grid[0].length];
        int component = 0;

        //dfs from every node 
        for(int i = 0 ; i < grid.length ;i++){

            for(int j = 0 ; j < grid[0].length ;j++){
                
                //if it is land and visited is false
                if(grid[i][j] == '1' && visited[i][j] == false){

                    dfs(grid , i , j , visited);
                    
                    component++;
                }
                
            }
        }

        return component;
    }

    public void dfs (char[][]grid , int i , int j , boolean[][] visited){
        
        //base case
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length
        || visited[i][j] == true || grid[i][j] == '0')
        return ;

            visited[i][j] = true;
            
            //going in all 4 directions

            dfs(grid , i , j+1 , visited);
            dfs(grid , i+1 , j , visited);
            dfs(grid , i-1 , j , visited);
            dfs(grid , i , j-1 , visited);
        
    }


}

class Solution {
    public int makeConnected(int n, int[][] connections) {
        //edge case - if we are given less than n-1 nodes to connect n nodes

        if(connections.length < n-1)
        return -1;

        /* 
        find no. of components in the graph(c) and assume them to be an 
        individual node , therefore we will need c-1 edges to connect them
        */
        int c = 0;

        //make a graph using HM
        HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();
        
        for(int connection[] : connections){
            int a = connection[0] , b = connection[1];

            graph.computeIfAbsent(a , k -> new ArrayList<>()).add(b);
            graph.computeIfAbsent(b , k -> new ArrayList<>()).add(a);
        }
        
        System.out.println(graph);
        //visited array 
        boolean visited[] = new boolean[n];
        
        //finding all components by using dfs on every node

        for(int i =0 ; i < n ; i++){

            if(visited[i] == false){
                
                if(graph.containsKey(i))
                dfs(graph , i , visited);

                c++;

            }
            
        }

        return c - 1;

        
    }

    public void dfs (HashMap<Integer,ArrayList<Integer>> graph , int source , 
    boolean[] visited ){

        
        visited[source] = true;

        for(int edge : graph.get(source)){
            if(visited[edge] == false)
            dfs(graph , edge , visited);
        }

        return ;
    }






}

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        
        /* we dont need visited in this question as input is provided uniquely*/
        
        List<List<Integer>> psf = new ArrayList<>(); //paths so far
        List<Integer> path = new ArrayList<>();        //current path

        //adding current edge
        path.add(0);

        //graph , source , destination , visited , paths so far
        dfs(graph, 0 , graph.length-1 ,psf , path);

        return psf;
    }

    public void dfs(int[][] graph , int source , int destination ,List<List<Integer>>psf ,List<Integer> path ){

        //adding path in the paths so far arraylist
        if(source == destination){
            psf.add(new ArrayList<>(path));
            return;
        }

        for(int edge : graph[source]){
            
            path.add(edge);  //adding current edge in current path
            
            //calling dfs for current edge
            dfs(graph , edge , destination , psf , path);

            //removing current edge as we explore different edges
            path.remove(path.size() - 1);
            
        }

        return;
    }   
}

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        //make HM for vertices and edges
        HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();

        for(int edge[] : edges){
            int a = edge[0] , b = edge[1];
            
            graph.computeIfAbsent(a , k -> new ArrayList<>()).add(b);
            graph.computeIfAbsent(b , k -> new ArrayList<>()).add(a);
        }

        //to prevent infinite loop between neighours
        boolean[] visited = new boolean[n];

        return dfs(graph , source , destination , visited);
    }

    //recursive  DFS
    public boolean dfs(HashMap<Integer,ArrayList<Integer>> graph,int source , 
    int destination , boolean visited[]){

        if(source == destination)
        return true;
        
        //mark the source first
        visited[source] = true;

        for(int edge : graph.get(source)){
            
            if(visited[edge] == false){

                if(dfs(graph , edge , destination , visited))
                return true;
            }
        }

        return false;
    }
}

class Solution {
    // Function to detect cycle in a directed graph.
    /* we will use topological sort for this , we will keep 2 boolean array visited and
    recursion_stack 
    
    if a cycle is present it will come in the recursion_stack , as its a DAG 
    
    Algo
    1) fire topological sort from all vertice 
    2) if from any vertice you find an already visited vertex in the same recursion , there is a cycle
    */
    public boolean isCyclic(int v, ArrayList<ArrayList<Integer>> graph) {
        boolean visited[] = new boolean[v];
        boolean recursion_stack[] = new boolean[v];
        
        for(int i = 0 ; i< v; i++){
            
            if(visited[i] == false){
                if(topo(graph,visited , recursion_stack , i))
                return true;
            }
        }
        
        return false;
    }
    
    public boolean topo(ArrayList<ArrayList<Integer>> graph , boolean visited[],boolean recursion_stack[] , int src){
        //if same vertex is coming again in the same recursion stack , there is a cycle
        if(recursion_stack[src] == true)
        return true;
        
        //an already visited vertex can come 
        if(visited[src] == true)
        return false;
        
        //marking vertex as visited in visited[] and current recursion_stack[]
        visited[src] = true;
        recursion_stack[src] = true;
        
        //adding neighours
        for(int edge : graph.get(src)){
            if(topo(graph , visited , recursion_stack , edge))
            return true;
        }
        
        //removing src from current recursion_stack while backtracking
        recursion_stack[src] = false;
        
        return false;
    }
    
    

//using kahn's algo 
    public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
        ans = new int[V];
        idx = 0;
        
        kahn(V , adj);
        
        return idx == V ? false : true;
    }
    static int ans[];
    static int idx ;
    public static void kahn(int v, ArrayList<ArrayList<Integer>> graph){
        
        //find indegree
        int indegree[] = new int[v];
        for(int i = 0 ;i < v ; i++){
            for(int edge : graph.get(i)){
                indegree[edge] ++;
            }
        }
        
        //add indegree 0 to q 
        Queue<Integer> q = new ArrayDeque<>();
        for(int i = 0 ;i < v ; i++){
            if(indegree[i] == 0)
            q.add(i);
        }
        
        //DAG no need of visited
        //fire BFS 
        while(q.size() > 0){
            int rem = q.remove();
            
            ans[idx] = rem;
            idx++;
            
            //reduce indegree of nbrs and add it in the q if 0
            //0 means no dependencies they can be printed
            for(int edge: graph.get(rem)){
                indegree[edge]--;
                
                if(indegree[edge] == 0)
                q.add(edge);
            }
        }
        
        
    }

class Solution {
    static int[] bellman_ford(int vtx, ArrayList<ArrayList<Integer>> edges, int s) {
        path = new int[vtx];
    
        return bellman(vtx , edges , s) == true ? path : new int[]{-1};
    }
    
    static int path[];
    public static boolean bellman(int vtx, ArrayList<ArrayList<Integer>> edges, int s){
        Arrays.fill(path , 100000000);
        path[s] = 0;
        boolean negative_wtcyle = false;
        
        //we need only v-1 iteration but we check till v iteration to check for negative
        //wt cycle
        for(int i = 0 ;i < vtx ; i++){
            
            for(ArrayList<Integer> edge : edges){
                int u = edge.get(0), v = edge.get(1) , wt = edge.get(2);
                
                if(path[u] == Integer.MAX_VALUE)
                continue;
                
                if(path[u] + wt < path[v]){
                    path[v] = path[u]+wt;
                    
                    //if at vth iteration distance get updated its negative wt cycle
                    if(i == vtx-1)
                    negative_wtcyle = true;
                }
                
            }
        }
        
        return negative_wtcyle == false ? true : false;
    }

class Solution {
    public int minCost(int[][] grid) {
        /* already submitted a solution using BFS and DP 
            this one is simple solution using Djikstra and DP

            //we will not use pair class instead use array and lambda function
        */

        int m = grid.length, n = grid[0].length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[2] - b[2]);
        q.add(new int[]{0 , 0 ,0});

        /* we will make a dp array which will store minimum cost for every cell , this is to avoid using visited..
        as a new path can overlap an old path if it has a lesser path cost we will make this a dp array and not
        visited cause then a new path will not be able to overlap a previous path as that cell will already be true
        */

        int[][] costs = new int[m][n];   //dp array
        
        for(int temp[] : costs)                      //filling dp array
        Arrays.fill(temp , Integer.MAX_VALUE);

        //djikstra algo
        while(q.size() > 0){
            int[] rem = q.remove();
            int row = rem[0] , col = rem[1] , cost = rem[2];

            if(row == m-1 && col == n-1)
            return cost;

            //seeing neighours
            for(int i = 0 ; i < 4 ; i++){
                int rowdash = row + dir[i][0];
                int coldash = col + dir[i][1];

                //if valid cell
                if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n ){
                    
                    /* if new cost is < previous cost we update even if we have to revsit the node  -- this is 
                    alternate to visited array */
                    int new_cost = cost + (i+1 == grid[row][col] ? 0 : 1);

                    if(new_cost < costs[rowdash][coldash]){
                        costs[rowdash][coldash] = new_cost;
                        q.add(new int[]{rowdash , coldash , new_cost});
                    }
                }
            }
        }

        return 69;
    }

    public int[][] dir = {{0,1}, {0,-1} , {1,0} , {-1,0}};  //right , left , down , up
    
}