{"id":"32166665-6349-4b83-87b4-341699331ade","name":"Mother Vertex","description":"Given a Directed Graph, find a Mother Vertex in the Graph (if present). \r\nA Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.","outputFormat":"Print the mother vertex if present else print -1.","constraints":"1&lt;= N &lt;= 10000\r\n1&lt;= M &lt;= (N*(N-1))/2\r\n1&lt;= ai, bi &lt;= N","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n\n\nint findMotherVertex(int n,vector<vector<int>> &adjlist)\n{\n}\n\nint main()\n{\n int n,m;cin>>n>>m;\n vector<vector<int>> adjlist(n);\n for(int i=0;i<m;++i)\n {\n int u,v;cin>>u>>v;\n adjlist[u-1].push_back(v-1);\n }\n cout<<findMotherVertex(n,adjlist)<<\"\\n\";\n return 0;\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\n\npublic class Main{\n \tpublic static void main(String args[]) throws Exception {\n\n\t\tBufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\t\tString[] st = br.readLine().split(\" \");\n\t\tint n = Integer.parseInt(st[0]);\n\t\tint m = Integer.parseInt(st[1]);\n\n\t\tArrayList<ArrayList<Integer>> graph = new ArrayList<>();\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tgraph.add(new ArrayList<>());\n\t\t}\n\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tst = br.readLine().split(\" \");\n\t\t\tint u = Integer.parseInt(st[0]) - 1;\n\t\t\tint v = Integer.parseInt(st[1]) - 1;\n\t\t\tgraph.get(u).add(v);\n\t\t}\n\n\t\tSystem.out.println(findMotherVertex(n, graph));\n\t}\n public static int findMotherVertex(int N, ArrayList<ArrayList<Integer>>adj){\n\t\n\n \t}\n \n \n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"4 3\r\n1 2\r\n2 3\r\n3 4","sampleOutput":"1\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"cd990e93-71dd-458c-9c80-95c393613140","name":"Mother Vertex","slug":"mother-vertex","type":1}],"next":{"id":"9edacc05-a8b0-44dd-a9cf-47ec4299485b","name":"Mother Vertex Hard MCQ","type":0,"slug":"mother-vertex-hard-mcq"},"prev":{"id":"b6273c41-b0a0-4c01-9b79-71d16647f1cc","name":"Minimize Hamming Distance After Swap Operations Medium","type":3,"slug":"minimize-hamming-distance-after-swap-operations-medium-8272"}}}

Mother Vertex

Given a Directed Graph, find a Mother Vertex in the Graph (if present). A Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.

{"id":"32166665-6349-4b83-87b4-341699331ade","name":"Mother Vertex","description":"Given a Directed Graph, find a Mother Vertex in the Graph (if present). \r\nA Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.","inputFormat":"First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.","outputFormat":"Print the mother vertex if present else print -1.","constraints":"1&lt;= N &lt;= 10000\r\n1&lt;= M &lt;= (N*(N-1))/2\r\n1&lt;= ai, bi &lt;= N","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\n\n\nint findMotherVertex(int n,vector<vector<int>> &adjlist)\n{\n}\n\nint main()\n{\n int n,m;cin>>n>>m;\n vector<vector<int>> adjlist(n);\n for(int i=0;i<m;++i)\n {\n int u,v;cin>>u>>v;\n adjlist[u-1].push_back(v-1);\n }\n cout<<findMotherVertex(n,adjlist)<<\"\\n\";\n return 0;\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\n\npublic class Main{\n \tpublic static void main(String args[]) throws Exception {\n\n\t\tBufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\t\tString[] st = br.readLine().split(\" \");\n\t\tint n = Integer.parseInt(st[0]);\n\t\tint m = Integer.parseInt(st[1]);\n\n\t\tArrayList<ArrayList<Integer>> graph = new ArrayList<>();\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\tgraph.add(new ArrayList<>());\n\t\t}\n\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tst = br.readLine().split(\" \");\n\t\t\tint u = Integer.parseInt(st[0]) - 1;\n\t\t\tint v = Integer.parseInt(st[1]) - 1;\n\t\t\tgraph.get(u).add(v);\n\t\t}\n\n\t\tSystem.out.println(findMotherVertex(n, graph));\n\t}\n public static int findMotherVertex(int N, ArrayList<ArrayList<Integer>>adj){\n\t\n\n \t}\n \n \n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"4 3\r\n1 2\r\n2 3\r\n3 4","sampleOutput":"1\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"cd990e93-71dd-458c-9c80-95c393613140","name":"Mother Vertex","slug":"mother-vertex","type":1}],"next":{"id":"9edacc05-a8b0-44dd-a9cf-47ec4299485b","name":"Mother Vertex Hard MCQ","type":0,"slug":"mother-vertex-hard-mcq"},"prev":{"id":"b6273c41-b0a0-4c01-9b79-71d16647f1cc","name":"Minimize Hamming Distance After Swap Operations Medium","type":3,"slug":"minimize-hamming-distance-after-swap-operations-medium-8272"}}}
plane

Editor

Loading...

Mother Vertex

easy

Given a Directed Graph, find a Mother Vertex in the Graph (if present). A Mother Vertex is a vertex through which we can reach all the other vertices of the Graph.

Constraints

1<= N <= 10000 1<= M <= (N*(N-1))/2 1<= ai, bi <= N

Format

Input

First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.

Output

Print the mother vertex if present else print -1.

Example

Sample Input

4 3 1 2 2 3 3 4

Sample Output

1

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode