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.

Input

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.

Output

For each test case, print "YES" if the adjusting is ok for any situation, otherwise "NO".

Sample Input

3 3
1 2
1 3
2 3

3 3
1 2
2 3
1 3

Sample Output

YES
NO

Note:

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]

Round 1:

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]

Round 2:

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]

Round 3:

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.

1个回答

caozhy      2017.09.15 23:45

The part-time parliament笔记

The Part-Time Parliament
The Part-Time Parliament This article appeared in ACM Transactions on Computer Sys- tems 16, 2 (May 1998), 133-169. Minor corrections were made on 29 August 2000. lamport
Peaceful Commission_hdu1814_2-sat
Problem Description The Public Peace Commission should be legislated in Parliament of The Democratic Republic of Byteland according to The Very Important Law. Unfortunately one of the obstacles
The_Part-Time_Parliament (Paxos算法中文翻译)
Paxos算法是分布式技术大师Lamport提出的，主要目的是通过这个算法，让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说，就是在一个选举过程中，让不同的选民最终做出一致的决定。 Lamport为了讲述这个算法，假想了一个叫做Paxos的希腊城邦进行选举的情景，这个算法也是因此而得名。在他的假想中，这个城邦要采用民主提议和投票的方式选出一个最终的决议，但由于城邦的居民没有人愿意把全部时间和精力放在这种事情上，所以他们只能不定时的来参加提议，不定时来了解提议、投票进展，不定时的表达自己的投票意见。Paxos算法的目标就是让他们按照少数服从多数的方式，最终达成一致意见。
HDOJ 1814 Peaceful Commission

Qs
&amp;lt;script src=&quot;https://cdn.bootcss.com/qs/6.5.1/qs.min.js&quot;&amp;gt;&amp;lt;/script&amp;gt;http://www.bootcdn.cn/qs/https://cdn.bootcss.com/qs/6.5.1/qs.min.jsQs.stringify(applyArr)
axios模拟表单POST请求 使用qs

qs.parse()、qs.stringify()使用方法
qs是一个npm仓库所管理的包,可通过npm install qs命令进行安装. 1. qs.parse()将URL解析成对象的形式 const Qs = require('qs'); let url = 'method=query_sql_dataset_data&amp;amp;projectId=85&amp;amp;appToken=7d22e38e-5717-11e7-907b-a6006ad3...

TeamViewerQS
TeamViewerQS是一种可以穿透防火墙的远程桌面软件！