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.
Input Format
First line contains an integer n.
Each of next n lines contain 2 numbers denoting a bidirectional edge between them.
Output Format
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.
Question Video
Constraints
1<= n <= 10000
number of edge = number of vertices
Sample Input
3
1 2
1 3
2 3
Sample Output
2 3


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name