In a computer network a link L, which interconnects two servers, is considered critical if there are at least two servers A and B such that all network interconnection paths between A and B pass through L. Removing a critical link generates two disjoint sub-networks such that any two servers of a sub-network are interconnected.

For example, the network shown in figure 1 has three critical links that are marked red: 0 - 1, 3 - 4 and 6 - 7 in figure 2.


Figure 1: Original Graph	Figure 2: The Critical Links

It is known that:

The connection links are bi-directional.
A server is not directly connected to itself.
Two servers are interconnected if they are directly connected or if they are interconnected with the same server.
The network can have stand-alone sub-networks.

Write a program that finds all critical links of a given computer network.

Input

Input starts with an integer T (≤ 15), denoting the number of test cases.

Each case starts with a blank line. The next line will contain n (0 ≤ n ≤ 10000) denoting the number of nodes. Each of the next n lines will contain some integers in the following format:

u (k) v₁ v₂ ... v_k

Where u is the node identifier, k is the number of adjacent nodes; v₁, v₂ ... v_k are the adjacent nodes of u. You can assume that there are at most 100000 edges in total in a case.

Output

For each case, print the case number first. Then you should print the number of critical links and the critical links, one link per line, starting from the beginning of the line, as shown in the sample output below. The links are listed in ascending order according to their first element and then second element. Since the graph is bidirectional, print a link u v if u < v.

Sample

Sample Input	Sample Output
Click to copy 3 8 0 (1) 1 1 (3) 2 0 3 2 (2) 1 3 3 (3) 1 2 4 4 (1) 3 7 (1) 6 6 (1) 7 5 (0) 0 2 0 (1) 1 1 (1) 0	Click to copy Case 1: 3 critical links 0 - 1 3 - 4 6 - 7 Case 2: 0 critical links Case 3: 1 critical links 0 - 1

Notes

Dataset is huge, use faster I/O methods.

LOJ 1026 - Critical Links

Suppose there is a interconnected network between several server or nodes, in these network some nodes are said to be critical link which generates two disjoint (there is no other path) sub-networks such that any two servers of a sub-network are interconnected.

Solution

It is a very basic problem in Bridge(graph) concept ...Actually we need to find how many bridges exists in this graph.Taking input of graph is interesting.First we construct graph and run DFS tree to find back edge and forward edge using discovery time and low time(means there another path exists). And finally make pair of vertices and print it.

Bridge concept: A bridge is defined as an edge which when romoved makes graphs disconnected. More precisely it increases number of connected components. Why we use DFS? The idea behind this is that it will create the simple structure of the graph and so we can easily determine back edge/forward edge. Back edge/forward edge is nothing but it says a node has multiple path to reach so we can confirm there is a cycle. A cyclic path can't be a bridge. Try to figure out.


#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
using namespace std;
vi g[10005];
int visit[10005],low[10005],in[10005];
vector<pair<int,int> > bridge;
int cnt,timer;
void dfs1(int s,int p)
{
    visit[s]=1;
    low[s]=in[s]=++timer;
    for(int i=0;i<g[s].size();i++)
    {
        if(g[s][i]==p)
            continue;
        else if(visit[g[s][i]])
            low[s]=min(in[g[s][i]],low[s]);
        else
        {
            dfs1(g[s][i],s);
            if(low[g[s][i]]>in[s])
            {
                cnt++;
                if(g[s][i]>s)
                bridge.pb(make_pair(s,g[s][i]));
                else
                bridge.pb(make_pair(g[s][i],s));
            }
            low[s]=min(low[g[s][i]],low[s]);
        }
    }

}
int main()
{
    int t,n,e,u,v,cs=0;
    char a,b,c;
    cin>>t;
    while(t--)
    {
        cnt=0,timer=0;
        cin>>n;
       for(int i=0;i<n;i++)
       {
           g[i].clear();
           visit[i]=0;
       }
       bridge.clear();
       for(int i=0;i<n;i++)
       {
           cin>>u;

           scanf("%c%c%d%c",&c,&c,&e,&c);
           while(e--)
           {
               cin>>v;
               g[u].pb(v);
               g[v].pb(u);
           }
       }
       for(int i=0;i<n;i++)
       {
           if(!visit[i])
           {
               dfs1(i,-1);
           }
       }
      // dfs1(0,-1);
       cout<<"Case "<<++cs<<":"<<endl;
       cout<<cnt<<" critical links"<<endl;
        sort(bridge.begin(), bridge.end());
       for(int i = 0; i <bridge.size(); i++)
       {
         cout << bridge[i].first << " - " << bridge[i].second << endl;
    }

    }


    return 0; 


}

Tutorial source

Input

Output

Sample

Notes

Total Submissions

Users Tried

Users Solved

LOJ 1026 - Critical Links

Solution