2 shunfurh 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
caozhy   Ds   Rxr 2017.09.15 23:45
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
The part-time parliament笔记
另一篇更详细的Paxos笔记:http://blog.csdn.net/m_vptr/article/details/8014220 每个议员手中有一本律簿 所有律簿上的法令都是一致的,也就是第x条法令的内容是一致的,当然可能有的律簿上还没有这条法令 律簿背面记录重要的笔记,不重要的笔记记在小纸条中,小纸条很有可能丢失。笔记代表机器在内存中的一些状态。 可能出现的问题:一拨
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
经典2sat裸题,dfs的2sat可以方便输出字典序最小的解... Peaceful Commission Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1578    Accepted Submission(s): 4
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插件构建1.安装qs:cnpm install qs2.引用模块import Qs from 'qs'3.构造数据var da1 =  Qs.stringify({   method:'value',});4.填入数据即可axios({   url:'/api/xxxxx/xxxx.xxx',   method:'post',   d...
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...
用python爬取QS大学排名(python代码+QS大学排名)
这是爬取QS大学排名的python代码,以及爬取下来的QS 大学排名。
TeamViewerQS
TeamViewerQS是一种可以穿透防火墙的远程桌面软件!