InMobi Supply Path Optimization Problem - Inmobi Online Assessment IIT BHU

Problem Preview

"In the ad-tech ecosystem, supply often flows through multiple intermediaries such as SSPs, exchanges, and resellers. Reselling is common, so an advertiser can often reach the same publisher through multiple different paths. However, some business relationships are absolutely critical — without them, entire publishers become unreachable. InMobi wants to identify these critical connections so that it only focuses on them and considers removing redundant ones. You are given an undirected graph representing the supply network: Each node is a supply partner (InMobi, SSP, exchange, publisher, advertiser). Each edge is a direct business relationship (integration or reselling). Node 0 represents InMobi. The graph is guaranteed to be a single connected component. A critical connection is an edge whose removal increases the number of disconnected components in the graph, i.e., without it, InMobi loses access to some publishers. Your task: Find and print all critical connections. A critical connection is an edge whose removal increases the number of disconnected components in the graph, i.e., without it, InMobi loses access to some publishers. All other edges are non-critical connections. --- Input Format The first line contains two integers n and m — the number of supply partners and business relationships. The next m lines each contain two integers u and v, denoting an undirected edge between partners u and v. Nodes are 0-indexed (0 <= u, v < n). --- Output Format Print all critical connections as pairs u v such that u < v. The output should be sorted lexicographically (first by u, then by v). If all connections are critical, print -1. --- Constraints 1 <= n <= 10^5 n - 1 <= m <= 2 × 10^5 0 <= u, v < n The graph is connected. --- Sample Input 4 4 0 1 1 2 2 0 1 3 Sample Output 1 3 Explanation Removing the edge (1, 3) disconnects node 3 from the rest of the graph, making it a critical connection. All other edges belong to a cycle, so removing any one of them does not disconnect the graph."