> 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/mother-vertex.md).

# Mother Vertex

Given a Directed Graph, find a Mother Vertex in the Graph (if present). 

**Input:**\
The first line of input contains an integer T. Then T test cases follow. Each test case contains two integers **V** (number of vertices) and **E** (number of edges). In the next line are **E** space separated values u,v denoting an edge from u to v.\
\
**Output:** For each testcase return the mother vertex of graph (if exists) else return -1.

**Your Task:**\
You don't need to read input or print anything. Your task is to complete the function **findMother()** which takes a Directed graph and the number of vertices as inputs and returns a Mother Vertex in the Graph. If the graph has mltiple Mother Vertices, return the one with the smallest value. If the Mother Vertex does not exist, return -1.

**Expected Time Complexity:** O(V + E).\
**Expected Auxiliary Space:** O(V).

**Constraints:**\
1 <= T <= 500\
1 <= V <= 500\
1 <= E <= 3000\
0 <= u, v < N

**Example:**\
**Input:**\
2\
5 5\
1 0 0 2 2 1 0 3 3 4\
3 2\
0 1 2 1

**Ouput:**\
0\
-1

**Explanation:**\
**Testcase 1:** According to the given edges, all nodes can be reaced from nodes from 0, 1 and 2. But, since we are traversing from node 0, so 0 is the output.

**Testcase 2:** According to the given edges, no vertices are there from where we can reach all vertices. So, output is -1.

```java
class MotherVertex {
    public static void fillStackDFS(int v, ArrayList<ArrayList<Integer>> graph, Stack<Integer> st, boolean[] visited) {
        visited[v] = true;
        for (int x : graph.get(v))
            if (!visited[x])
                fillStackDFS(x, graph, st, visited);
        st.push(v);
    }

    public static void fillStack(ArrayList<ArrayList<Integer>> graph, Stack<Integer> st) {
        boolean visited[] = new boolean[graph.size()];
        for (int i = 0; i < graph.size(); i++)
            if (!visited[i])
                fillStackDFS(i, graph, st, visited);
    }

    public static int countDFS(ArrayList<ArrayList<Integer>> graph, int sv, boolean[] visited) {
        int count = 1;
        visited[sv] = true;
        for (int x : graph.get(sv))
            if (!visited[x])
                count += countDFS(graph, x, visited);
        return count;
    }

    static int findMother(ArrayList<ArrayList<Integer>> graph, int n) {
        Stack<Integer> st = new Stack<>();
        fillStack(graph, st);
        // As we are doing DFS in sorted order of nodes (when filling stack)
        // then the mother vertex will be at top of stack (if mother vertex is present)
        int sv = st.pop();
        boolean visited[] = new boolean[graph.size()];
        int coveredNodes = countDFS(graph, sv, visited);
        if (coveredNodes == n)
            return sv;
        return -1;
    }
}
```