{"id":"bf7f17e7-a514-4fac-814a-0a166fec69d2","name":"Redundant Connection 2","description":"You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph.\r\nReturn an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.\r\n\r\nNote : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain 2 numbers denoting a bidirectional edge between them.","outputFormat":"Print the edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.","constraints":"1&lt;= n &lt;= 10000\r\nnumber of edge = number of vertices","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>findRedundantDirectedConnection(vector<vector<int>>&edges){\n //write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<vector<int>>pos(n,vector<int>(2));\n \n for(int i=0;i<n;i++){\n cin>>pos[i][0];\n cin>>pos[i][1];\n \n }\n \n vector<int> ans=findRedundantDirectedConnection(pos);\n \n cout<<ans[0]<<\" \"<<ans[1];\n}"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static void main(String[] args) throws NumberFormatException, IOException {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int n = Integer.parseInt(st[0]);\r\n\r\n int[][] pos = new int[n][2];\r\n for (int i = 0; i < n; i++) {\r\n st = br.readLine().split(\" \");\r\n pos[i][0] = Integer.parseInt(st[0]);\r\n pos[i][1] = Integer.parseInt(st[1]);\r\n }\r\n\r\n int[] ans = findRedundantDirectedConnection(pos);\r\n System.out.println(ans[0] + \" \" + ans[1]);\r\n }\r\n\r\n\r\n\r\n public static int[] findRedundantDirectedConnection(int[][] edges) {\r\n\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n1 2\r\n1 3\r\n2 3\r\n","sampleOutput":"2 3\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":"7d95a9ef-abb5-4326-b2e1-e8c9d7527434","name":"Redundant Connection 2","slug":"redundant-connection-2","type":1}],"next":{"id":"af24a092-1387-4479-97d2-b9361108d201","name":"Redundant Connection 2 Hard MCQ","type":0,"slug":"redundant-connection-2-hard-mcq"},"prev":{"id":"fd9b2827-9318-4283-a5cb-e875514a340b","name":"Reconstruct Itinerary","type":3,"slug":"reconstruct-itinerary"}}}

Redundant Connection 2

You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input. Note : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.

{"id":"bf7f17e7-a514-4fac-814a-0a166fec69d2","name":"Redundant Connection 2","description":"You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph.\r\nReturn an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.\r\n\r\nNote : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain 2 numbers denoting a bidirectional edge between them.","outputFormat":"Print the edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.","constraints":"1&lt;= n &lt;= 10000\r\nnumber of edge = number of vertices","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>findRedundantDirectedConnection(vector<vector<int>>&edges){\n //write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<vector<int>>pos(n,vector<int>(2));\n \n for(int i=0;i<n;i++){\n cin>>pos[i][0];\n cin>>pos[i][1];\n \n }\n \n vector<int> ans=findRedundantDirectedConnection(pos);\n \n cout<<ans[0]<<\" \"<<ans[1];\n}"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static void main(String[] args) throws NumberFormatException, IOException {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int n = Integer.parseInt(st[0]);\r\n\r\n int[][] pos = new int[n][2];\r\n for (int i = 0; i < n; i++) {\r\n st = br.readLine().split(\" \");\r\n pos[i][0] = Integer.parseInt(st[0]);\r\n pos[i][1] = Integer.parseInt(st[1]);\r\n }\r\n\r\n int[] ans = findRedundantDirectedConnection(pos);\r\n System.out.println(ans[0] + \" \" + ans[1]);\r\n }\r\n\r\n\r\n\r\n public static int[] findRedundantDirectedConnection(int[][] edges) {\r\n\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n1 2\r\n1 3\r\n2 3\r\n","sampleOutput":"2 3\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":"7d95a9ef-abb5-4326-b2e1-e8c9d7527434","name":"Redundant Connection 2","slug":"redundant-connection-2","type":1}],"next":{"id":"af24a092-1387-4479-97d2-b9361108d201","name":"Redundant Connection 2 Hard MCQ","type":0,"slug":"redundant-connection-2-hard-mcq"},"prev":{"id":"fd9b2827-9318-4283-a5cb-e875514a340b","name":"Reconstruct Itinerary","type":3,"slug":"reconstruct-itinerary"}}}
plane

Editor


Loading...

Redundant Connection 2

easy

You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input. Note : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.

Constraints

1<= n <= 10000 number of edge = number of vertices

Format

Input

First line contains an integer n. Each of next n lines contain 2 numbers denoting a bidirectional edge between them.

Output

Print the edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example

Sample Input

3 1 2 1 3 2 3

Sample Output

2 3

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode