Medium Graph Theory > Cycles/Topological Sorting/Strongly Connected Component
All the houses of Westeros have prepared themselves for the war. Some houses have alliance with other houses and some have alliance with none. Alliance between two houses is not both way. That means if house Tarley have their alliance with house Tyrell, then Tyrells can’t have alliance with Tarleys. It doesn’t make any sense! But since Bran is messing with the past nowadays, all have gone mad. ------ Given names of n houses, and m alliances between them we need to know how many camps can be formed. A camp consists of one or more houses. Only condition is the houses need to have alliance dependency with every other houses of the camp. If house Stark have their alliance with house Arryn, then Starks have alliance dependency with Arryns. If Arryns have their alliance with house Tully, then Arryns have alliance dependency with house Tully and Starks also have alliance dependency with house Tully. Now if house Tullys have alliance with the Starks, Tullys will have alliance dependency with Stark. Since Arryns already have alliance dependency on the Tullys, they will also have alliance dependency with the Starks. Since all houses now have alliance dependency with each other, they can form a camp. ------ After getting the camps, we need to find if there exists such a camp which has more member houses than rest of the camps combined. If such case occurs then that large camp will make the other camps join their forces and fight the White Walkers. Otherwise no one will listen to anyone and fight will continue. And they will be doomed. ------ Input: ------ First line of the input is the test case number **T.( 1 <= T <= 14)**. Next T set of lines each have two integers **n ( 1 <= n <= 100000 )** and **m ( 1 <= m <= min(100000, n*(n-1)/2 ))** followed by m lines which contain 2 strings **u, v ( 1 <= |u|,|v| <= 10 ).** It means house u has alliance with house v. String u, v consists only of lowercase english letter. ---------- String u, v consists only of lowercase English letter. Output: ------- If no camp has more members than rest of the houses, output “**Doomed**.”. Otherwise output “**Fight the white walkers.**” Sample Input ------------ 3 6 6 Stark Tully Arryn Stark Tully Arryn Bolton Lannister Lannister Tyrell Tyrell Bolton 6 3 Stark Tully Arryn Stark Tully Arryn 5 3 Stark Tully Arryn Stark Tully Arryn Sample Output ------------- Doomed. Doomed. Fight the white walkers.