Bees are one of the most industrious insects. They collect nectar and pollen from the flowers and thus they rely on the trees in the forest. For better navigability, they numbered the n trees from 0 to n - 1. Instead of roaming around all over the forest, they use a predefined map consisting of some paths. A path is based on two trees, and the bees fly from one tree to another in a straight line. They don't use paths that are not on their map.

As technology has been improved a lot, they also changed their working strategy. Instead of hovering over all the trees in the forest, they are targeting particular trees, mainly trees with lots of flowers. To make things even better, they are planning to build some new hives on some targeted trees. Once done, they will only collect pollens from those trees and the unnecessary paths will be removed from their map.

Now, they want to build the hives such that if one of the paths in their new map become unavailable (some birds or animals interrupting them in that path), it's still possible to go from any hive to another using the other paths in their new map.

The bees don't want to choose less than two trees and they also want to build minimum number of hives. Now you are given the trees with the current map, your task is to propose a new bee hive colony for them.

Input

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

Each case starts with a blank line. Next line contains two integers n (2 ≤ n ≤ 500) and m (0 ≤ m ≤ 20000), where n denotes the number of trees and m denotes the number of paths. Each of the next m lines contains two integers u v (0 ≤ u, v < n, u ≠ v) meaning that there is a path between tree u and v. Assume that there can be at most one path between any pair of trees.

Output

For each case, print the case number and the number of beehives in the proposed colony or impossible if it's impossible to find such a colony.

Sample

Sample Input	Sample Output
Click to copy 3 3 3 0 1 1 2 2 0 2 1 0 1 5 6 0 1 1 2 1 3 2 3 0 4 3 4	Click to copy Case 1: 3 Case 2: impossible Case 3: 3

Notes

Dataset is huge, use faster I/O methods.
For case 3, the bees will build 3 hives in node {1, 2, 3} and they will only maintain three roads in the colony - {(1, 2), (1, 3), (2, 3)}.

LOJ 1437 - Beehives

Summary

In this problem, you have to built bee-hive in such a way that if one path is destroyed bee-hives will be still connected to each other by other path. Also at least 2 hive must be built.

Hint

You have to find shortest cycle in an undirected and unweighted graph. If you can't find one it will be impossible to built.

Prerequisites : BFS

Solution

Approach

For every node, we check if it is possible to get the shortest cycle involving this node. We run bfs from each node, for a back-edge, we consider the cycle it poses in our result. First push current node into the queue and then if node which is already visited comes again but it is not the parent node then the cycle is present.

Also note that, the cycles that we may consider might not be actual cycles (cycles + a prolonged line of vertices), but in case they are not, they'll not contribute to the result. See this picture below.

If we run bfs on node 0, there will be a cycle(1-2-3-5-4-1) + a prolonged line of vertices(0-1) but it will not contribute to the result because when we run bfs in node 1 or any other node within the cycle, it will be smaller.

Apply the above process for every node and find the length of the shortest cycle.

Time Complexity: O(|V|(|V|+|E|)) for a graph G=(V, E) per test case.
Memory Complexity: O(V^2) for a graph G=(V, E) per test case.

Code

C++


#include <bits/stdc++.h>
using namespace std;

const int N = 510 ;

vector <int> graph[N];
int ans ;

int shortest_cycle(int n) 
{ 
    ans = INT_MAX; 

    for (int i = 0; i < n; i++) { 

        vector<int> dist(n, INT_MAX ); 
        vector<int> par(n, -1); 
        queue<int> q; 

        dist[i] = 0; 
        q.push(i); 

        while (!q.empty()) { 

            int x = q.front(); 
            q.pop(); 

            for (int child : graph[x]) { 

                if (dist[child] == INT_MAX ) { 
                    dist[child] = 1 + dist[x]; 
                    par[child] = x; 
                    q.push(child); 
                } 

                else if (par[x] != child ) {
                    ans = min(ans, dist[x] + dist[child] + 1); 
                }

            } 
        } 
    }
} 

void _main_main()
{

    int n , m ; cin >> n >> m ;

    for (int i = 0; i < n; i++) graph[i].clear() ;
    for (int i = 0; i < m; i++) {
        int x , y ; cin >> x >> y ;
        graph[x].push_back(y) ;
        graph[y].push_back(x) ;
    }

    shortest_cycle(n) ;
    if (ans == INT_MAX) cout << "impossible\n" ;
    else cout << ans << "\n" ;

}



int main ()
{
    int testCase = 1 ; cin >> testCase ;
    for (int i = 0; i < testCase; i++){
        cout << "Case " << i+1 << ": " ;
        _main_main() ;
    }

}

Happy Coding!

Written by: Moontasir Mahmood

Tutorial source