{"id":"be514e2a-fc2d-4218-84ee-df09d5b607e2","name":"Redundant Connection","description":"You are given a 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 an 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","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\n vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n \n }\n\n int main(){\n int n;\n cin>>n;\n vector<vector<int>>pos(n,vector<int>(2));\n for (int i = 0; i < n; i++) {\n cin>>pos[i][0];\n cin>>pos[i][1];\n }\n\n vector<int>ans=findRedundantConnection(pos);\n cout<<ans[0]<<\" \"<<ans[1]<<endl;\n \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 = findRedundantConnection(pos);\r\n System.out.println(ans[0] + \" \" + ans[1]);\r\n }\r\n\r\n public static int[] findRedundantConnection(int[][] edges) {\r\n\r\n }\r\n\r\n private static int find(int[] parent, int f) {\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":"12087a8b-cf6e-4564-a44e-e0edacd89fe0","name":"Redundant Connection","slug":"redundant-connection","type":1}],"next":{"id":"7c4b31a3-62e8-4c62-94b8-e23442ca98a3","name":"Redundant Connection MCQ","type":0,"slug":"redundant-connection-mcq"},"prev":{"id":"e87d6769-314d-42e1-a5fc-734d4d4c2d42","name":"Negative Weight Cycle Detection","type":3,"slug":"negative-weight-cycle-detection"}}}

Redundant Connection

You are given a 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 an 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.

{"id":"be514e2a-fc2d-4218-84ee-df09d5b607e2","name":"Redundant Connection","description":"You are given a 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 an 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","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\n vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n \n }\n\n int main(){\n int n;\n cin>>n;\n vector<vector<int>>pos(n,vector<int>(2));\n for (int i = 0; i < n; i++) {\n cin>>pos[i][0];\n cin>>pos[i][1];\n }\n\n vector<int>ans=findRedundantConnection(pos);\n cout<<ans[0]<<\" \"<<ans[1]<<endl;\n \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 = findRedundantConnection(pos);\r\n System.out.println(ans[0] + \" \" + ans[1]);\r\n }\r\n\r\n public static int[] findRedundantConnection(int[][] edges) {\r\n\r\n }\r\n\r\n private static int find(int[] parent, int f) {\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":"12087a8b-cf6e-4564-a44e-e0edacd89fe0","name":"Redundant Connection","slug":"redundant-connection","type":1}],"next":{"id":"7c4b31a3-62e8-4c62-94b8-e23442ca98a3","name":"Redundant Connection MCQ","type":0,"slug":"redundant-connection-mcq"},"prev":{"id":"e87d6769-314d-42e1-a5fc-734d4d4c2d42","name":"Negative Weight Cycle Detection","type":3,"slug":"negative-weight-cycle-detection"}}}
plane

Editor


Loading...

Redundant Connection

easy

You are given a 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 an 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.

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