All submissions for this problem are available.
pK has landed on Earth. Two things are worrying him right now:
1. His "Remote control", that has been stolen by Tapaswi Maharaj.
2. The Religious/communal clashes among people in the earth.(None of them are 'Athiests' & there are atleast two religions being followed)
God feeling pity, gives pK a chance to bring an end to these communal clashes between Humans.
To start with, God creates 'C' cities (for C religions). He then assigns each person to their respective cities on the basis of the religion that they
follow. And people belonging to a particular city are bound to obey their "City Heads". He also builds individual "Passages" between each pair of cities.
In order to increase the integrity among people of different cities, God arranges a meeting inviting the "City Heads" of all the cities, requesting them to be peaceful
with each other. Though many of the city heads mutually accepted this request of God, there were still some pairs of "City Heads" who were reluctant to be friendly
with each other. God names the passages between these cities as "Antagonistic" passages & the rest as "Friendly" passages.
pK feared the existence of Antagonistic passages in the earth. God planned a re-Arrangement so as to transfer some cities to pK's planet such that these
conditions are satisfied:
1) No Antagonistic passages are allowed to exist solely inside the Earth.
2) No Friendly passages are allowed to exist solely inside pK's planet(So that pK could concentrate in avoiding clashes at Antagonistic passages).
3) Both these passages are allowed to exist between Earth and pK's planet.(So that both pK and God could take care of the clashes in Antagonistic passages of this
4) Both the earth and pK's planet must be non empty.(No partiality).
5) It is not necessary for every city in pK's planet to have a passage to earth's cities.
If such an arrangement is not possible,some communal clash and loss of life is bound to occur.
Wicked Tapaswi Maharaj prays & hypnotizes God, attaining power to even destroy a city that exists in earth or pK's planet. He decides to destroy zero or more cities
(and thus the passages linked with those cities)so that the above arrangement being planned by God gets hampered & some communal clash occurs.Even if he destroy a single
city he must be returning the "Remote control" to pK. (Considered by God as Tapaswi's sacrifice :/)
Whatsoever, the power attained by Tapaswi is such that it gets exhausted when the total number of cities becomes two or less than that.
pK is said to have succeeded if he saves people's life by avoiding any clash from occuring.Or otherwise wicked Tapaswi is said to have succeeded.
The first line consists of an integer T(1<=T<=100), the number of test cases. T test cases follow :
The first line of each test case contains two integers C & A.
'C'-> No. of cities.(2<=C<=200)( Cities being labelled from 0 to C-1 )
'A'-> No. of Antagonistic passages.
'A' lines follow,each containg two integers c1 & c2(0<=c1,c2<=C-1), the indexes of cities between which such a passage exists.
Each test case consists of two lines of output.
First Line consists of either of the two strings "pK triumphs" or "Tapaswi Maharaj triumphs" on respective cases.
Second Line contains the information about the current status of the "Remote control",i.e,either of the two strings "Remote control lies with Tapaswi" or "pK gets back
his Remote control". (Quotes for clarification).
Input: 1 4 2 0 2 1 3 Output: Tapaswi Maharaj triumphs Remote control lies with Tapaswi
Tapaswi need not destroy any city this time, as such an arrangement following the conditions is not possible with the given set of Antoganistic passages
|Time Limit:||0.4 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.