shunfurh 于 2017.08.31 19:55 提问
- QS Parliament
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.
In each test case, the first line will contains two positive numbers N (1 <= N <= 15), M (M <= 500). N is the number of QS's, M is the number of fight rounds.
Each of the following M lines contains two numbers Ai and Bi, which define the numbers in this round.
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.
Assume the three QS's : QS1 QS2 QS3, and QS3 is stronger than QS2, QS2 is stronger than QS1. And at first QS1 gets the metal-card with number 1 on, QS2 gets 2, QS3 gets 3.
original distribution: QS1[No.1 card] QS2[No.2 card] QS3[No.3 card]
card : No.1 card <> No.2 card
QS : QS1 <> QS2
result: QS2 wins this round and gets No.1 card, QS1 gets No.2 card
distribution: QS1[No.2 card] QS2[No.1 card] QS3[No.3 card]
card : No.2 card <> No.3 card
QS : QS1 <> QS3
result: QS3 wins this round and gets No.2 card, QS1 gets No.3 card
distribution: QS1[No.3 card] QS2[No.1 card] QS3[No.2 card]
card : No.1 card <> No.3 card
QS : QS2 <> QS1
result: QS2 wins this round and gets No.1 card, QS1 gets No.3 card
final distribution: QS1[No.3 card] QS2[No.1 card] QS3[No.2 card]
QS3 is stronger than QS2, but gets a worse card finally, so this adjusting is not ok for the situation we assumed above.
- caozhy 2017.09.15 23:45