ZOJ Problem Set - 1621
On a mystery island lives a tribe. What we only know about it is that the name of the resident on this island is QS. Recently, we payed attention to a special local activity among these QS's (pl.). They have an organization just like our parliament, each QS has its own power in the tribe, and no two QS's have the same power. To denote the power, each QS will gets a metal-card with a number on it, the less the number is, the bigger the power it denotes.
When a new year is coming, all QS's will fight for a better metal-card (with a less number). At first, each QS will get a random metal-card among all cards (with the number 1 to N). Then, there will be several rounds of fight to adjust the distribution. In each round, they will select two numbers A and B (range from 1 to N), and the current owners of these two numbers will fight with each other. Then the stronger QS will get the less number, on the contrary the weaker one will get the bigger one. Assume that there will be no draw.
Now, our question is that, after the adjusting, whether they can be assured that all the QS's will get their appropriate positions. It means that no such situation occurs: one QS is stronger than another but gets a bigger number finally.
There are several test cases.
Process to the end of input.
For each test case, print "YES" if the adjusting is ok for any situation, otherwise "NO".
Let's take the second sample input to explain why it is not ok.
original distribution: QS1[No.1 card] QS2[No.2 card] QS3[No.3 card]
QS3 is stronger than QS2, but gets a worse card finally, so this adjusting is not ok for the situation we assumed above.
Author: ZHENG, Jianqiang
Source: Zhejiang University 2003 Summer Camp Qualification Contest