Island of Demons

KIRIN29 Replay of Intra AUST Prog...
Limits 1s, 512 MB

During the war of the human, elves and dwarves, there rose a glade in an unknown region with multiple small islands. Which slowly began to fill with nameless monsters and demons. Their soul purpose was to destroy the three realms (human, elves, dwarves).
The three realm came together a plan to destroy those mysterious islands in one swoop. Elven king Thranduil cast a powerful magic in all over the islands linking them one another with an one directional portal. The idea was to fire all sorts of weapon, cast all sorts of magic from all the realms through the portal to destroy the islands instantly.
But the restriction is that they could use only one portal to fire. Hence they had to carefully find out which portal will destroy all the islands.

Suppose there are four islands as the above picture. Only from island 1 all the other islands are accessible via Thranduil’s portal. Hence the desired portal will be placed on island 1
Note:
You can be sure that there is at least one island and there can only be one desired island for placing portal or none at all!!

Input

First line of input will contain T (<=100) the number of test cases. Then the description of test cases follows.

The first line of each test case contains two integers N (0 < N <= 1000000) - the number of islands and M ( 0 <= M <= 1000000) - the number of connections. Next M line will contain two integers x & y (1 <= x, y <= N) which denotes the the island’s connectivity from island x to island y.

Sum of N+M over all test cases will be at most 1000000.

Output

For each case print the desired island as Case #t: The desired island is x, where t denotes the test case number and x denotes the island’s number. In case there can’t be found any desired island, just print Case #t: Doomed!

Sample

InputOutput
1
4 3
1 2
1 4
1 3
Case #1: The desired island is 1

Submit

Login to submit.

Statistics

60% Solution Ratio
Sarwar.445674Earliest, 4M ago
Sajjat004Fastest, 0.1s
Sajjat004Lightest, 7.2 MB
fire_tornadoShortest, 1103B
Toph uses cookies. By continuing you agree to our Cookie Policy.