It is year 3001, and the Klingon Empire has decided to invade Earth. Being a race of honour, the Klingons have decided to advance by foot to comquer Earth acre by acre. At last, the Klingons have marched to the lower mainland / fraser valley area.
Vancouver is by no means ready for this cruel bloody invasion! It needs time to prepare and make phone calls to Victoria, who then needs time to make phone calls to Ottawa. It is then up to the lower mainland residents to slow the advance of the Klingon army.
Fortunetly for Earth as a whole, their ancestors was able to to forsee this disaster and make adequate preparations. As early as the 19th century, people worked day and night to pollute all the rivers, lakes, and oceans. So, by 3001, the water is so dirty that the Klingons dare not touch it.
The Fraser river cuts through the lower mainland in many places. Without the bridges, there is no way for the Klingons to cross the rivers while not touching Earth water. Thus, to slow down the Klingon advance, the residents have decided to take out the bridges in lower mainland.
Unfortunately, in this age of war, explosives are expensive and come in limited quantities. Thus the residents have decided to blow up the critical bridges first. A bridge is critical if, without the bridge, parts of the lower mainland that was connected become seperated. Local residents have create a graph that represents the lower mainland, with nodes being separate pieces of land, and edges being the bridges. Given this graph, you are to find out which bridges are critical.
For example, in the following figure, the critical bridges are bolded: 0-1, 3-4, 6-7.
There will be multiple test cases. The first line will contain an integer n equal
to the number of test cases.
For each test case, the first line will contain two integers v, e, representing the number of land pieces and bridges (1 <= v <= 1000). After this will be e lines each containing two integers (0 to v-1) representing a bridge between the two land pieces.
For each test case, first print the case number as shown in sample output. Then, print the critical bridges in the following form:
If there are no critical bridges, write "No critical bridges." in a line
3 8 6 0 1 1 2 1 3 2 3 3 4 6 7 7 6 0 1 1 2 2 3 3 4 4 6 4 5 3 3 0 1 0 2 1 2
Case #1: 0 1 3 4 6 7 Case #2: 0 1 1 2 2 3 3 4 4 5 4 6 Case #3: No critical bridges.