完全排序网络

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file sortingnet.in Output file sortingnet.out

【题目描述】


排序网络是这样一个模型:

有n条水平的导线,由上至下分别标号为1至n,导线与导线之间不相交。在任意两导线之间可以搭上“电桥”。每条导线的左端放置一数字,数字沿导线由左向右同步运行,当遇上一电桥时,比较电桥两端的两根导线上的数字,将其中较大的放到上面的导线上,而将较小的放到下面的导线上,然后继续运行,保证同一时刻最多只有一个电桥。(如图)

若一个n行的排序网络共包含m个电桥,对于左端输入的任意顺序的数列,都能在右端得到一个由大到小的数列,我们称这个排序网络是一个完全排序网络。

我们的程序需要做的,就是判断一个排序网络是否是一个完全排序网络。


【输入格式】

第一行是一个整数N,表示排序网络的行数

第二行是一个整数M,表示排序网络的电桥数

接下来的M行,每行有两个整数i,j,表示导线i和j之间有一条电桥。

电桥按从左向右的顺序依次给出。

【输出格式】

一行。若这个排序网络是完全排序网络,那么输出"Yes!",否则输出"No!"。

当然,你的输出中不包含引号

【样例输入】

6
15
1 2
2 3
3 4
4 5
5 6
1 2
2 3
3 4
4 5
1 2
2 3
3 4
1 2
2 3
1 2

【样例输出】

Yes!

【提示】

样例描述了一个等价于N=6的冒泡排序法的排序网络
对于40%的数据,N<=10,M<=100
对于100%的数据,N<=100,M<=200000

【来源】

NOI1999北京集训队训练题
杨江明,《论数学策略在信息学问题中的应用》,IOI2000国家集训队论文集