SP22316 RELIGION - pK

**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 amoing 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 type). 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(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. **Input**: The first line consists of an integer **T**(1

N/A

N/A