Doctor Strange

Kamar-taj is a place where "The Acient One" trains people to protect earth from other dimensions. The earth is protected by 'n' sanctums, destroying any of it will lead to invasion on earth. The sanctums are connected by 'm' bridges. Now , you being on dormammu's side , want to finds no of sanctum destroying which will disconnect the sanctums.

Input: First line of the input contains T the number of test cases. First line of each test case contains n(no of sanctums) and m(no of bridges). Each m line of test case contains p and q denoting sanctum p is connected to sanctum q.

Output: Each new line of the output contains no of sanctums when destroyed will disconnect other sanctums of Earth .

Constraints:

1 ≤ T ≤ 100 1 ≤ n ≤ 30000 1 ≤ m ≤ 30000 1 ≤ p,q ≤ n

Example: Input: 1 5 5 1 2 1 3 3 2 3 4 5 4

Output: 2

class GFG {
    // Function to count number of articulation points
    // In undirected connected graph
    static int[] low, discovery;
    static int time, count;

    public static int findArticulationPoints(List<Integer>[] graph, int n) {
        boolean visited[] = new boolean[n];
        // Starting DFS from 0th vertex
        low = new int[n];
        discovery = new int[n];
        time = 0;
        count = 0;
        DFS(graph, 0, -1, visited);
        return count;
    }

    public static void DFS(List<Integer>[] graph, int node, int parent, boolean[] visited) {
        low[node] = time;
        discovery[node] = time;
        time++;
        visited[node] = true;
        int dfsCalls = 0;
        boolean isAP = false;
        for (int neighbor : graph[node]) {
            if (neighbor == parent)
                continue;
            if (visited[neighbor])
                low[node] = Math.min(low[node], discovery[neighbor]);
            else {
                DFS(graph, neighbor, node, visited);
                low[node] = Math.min(low[node], low[neighbor]);
                if (discovery[node] <= low[neighbor] && !isAP && node != 0) {
                    isAP = true;
                    count++;
                }
                dfsCalls++;
            }
        }
        // 0th node is our startng point, therefore with above formula it will always be
        // AP
        // which might not be true, therefore we check the number of components
        // connected to this node
        // Therefore if components>=2, then this node will also be an AP
        if (node == 0 && dfsCalls > 1) {
            count++;
        }
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while (t-- > 0) {
            int n = s.nextInt();
            List<Integer>[] graph = new ArrayList[n];
            for (int i = 0; i < n; i++)
                graph[i] = new ArrayList<>();
            int e = s.nextInt();
            for (int i = 0; i < e; i++) {
                int u = s.nextInt() - 1;
                int v = s.nextInt() - 1;
                graph[u].add(v);
                graph[v].add(u);
            }
            System.out.println(findArticulationPoints(graph, n));
        }
        s.close();
    }
}