ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. War and Peace

Time limit: 1.0 second
Memory limit: 64 MB
During the war in Erathia, an army of liches had to solve a difficult task of relocating its troops. Liches can teleport from one city to another quickly enough, but giving directions to thousands of liches in dozens of strongholds seems to be a real problem. This problem was especially difficult when the Great lich Sandro was powerful, as the army of liches grew huge.
Sandro noticed that only two of all the spells, Curse of the Netherworld and Implosion, are powerful enough. When somebody casts them, it can be felt everywhere in the country. He decided to use these spells as signals to his troops. When liches in a certain stronghold feel a certain spell, they should teleport to the predefined destination stronghold (or stay in their current stronghold). After a spell is cast, the liches in all the strongholds simultaneously teleport according to this scheme. Liches have no troubles with discipline, so this scheme works perfectly since it was introduced.
When Sandro died, the peace between people and the undead was proclaimed. The remaining liches were evenly distributed among all the strongholds in Deyja in case of a sudden attack, while the top undead commanders started to fight for power. Soon necromancer Vidomina and vampire Korbu became the most powerful among the undead. Their influence was almost equal, so none of them could become the only leader, and the country was split between them. Recently, Vidomina decided to start another war against Erathia and began to gather troops. As an experienced warlord, she understands the strength of Erathia's army, and now wants to gather all the troops in one stronghold prior to the attack. Meanwhile, Korbu thinks that this war can lead to total annihilation of the undead and wants to keep truce. He can't convince Vidomina, so he decided to prevent her from gathering all the troops together.
Casting signal spells requires a lot of energy, so they can only be cast once a day. Each noon Vidomina casts one of the spells, in order to gather the liches together. On the other hand, each midnight Korbu also casts one of the spells, trying to stop Vidomina. There are no other mages capable of casting these spells in Deyja, so no one else can move the troops. Vidomina casts her spell first. Assuming that both mages act optimally, find out whether Vidomina succeeds in gathering all the liches together.


The first line contains an integer n, the number of strongholds in Deyja (2 ≤ n ≤ 1000). The i-th of the following n lines contains two integers ai and bi which are the numbers of strongholds where troops move from stronghold i after Curse of the Netherworld and Implosion spells, respectively (1 ≤ ai, bin).


Output “War” if Vidomina will succeed in gathering all the troops together, or “Peace” if Korbu will prevent her from doing that in any finite number of days.


2 1
1 2
2 2
2 1
Problem Author: Fedor Fominykh
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
To submit the solution for this problem go to the Problem set: 1856. War and Peace