> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/doctor-strange.md).

# 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

```java
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();
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/doctor-strange.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.