UOJ Logo Universal Online Judge

UOJ

#168. 【UR #11】元旦老人与丛林

统计

零点的钟声马上就要敲响,2016 年即将要拉开序幕,元旦老人轻手轻脚地来到了 shanquan2 的床头,准备把他的礼物装进袜子里。

然而,shanquan2 的礼物居然是一张无向图!无向图怎么才能装进袜子里呢?这让元旦老人犯了难。

经过研究,元旦老人发现:只有满足一定条件的无向图才能被装进袜子里。

对于一张 $n$ 个点 $m$ 条边的无向图,你可以选出若干条边(可以全选也可以不选),如果存在一种方案使得无论是只保留所有你选出的边还是只保留所有你没有选出的边,这张无向图都是一个森林(即没有环),那么这张无向图被称为丛林。

元旦老人发现只有丛林才能够被装进袜子里!然而留给元旦老人的时间已经所剩无几了,情急之下,他决定向你寻求帮助:判断一张无向图是不是丛林。

输入格式

第一行两个正整数 $n,m$。

接下来的 $m$ 行每行两个正整数 $u,v(1 \leq u,v \leq n)$,表示图中的一条无向边。

注意:这张图可能存在重边和自环。

输出格式

仅输出一行一个字符串,如果这张图是丛林,输出 Yes,否则输出 No。

样例一

input

2 2
1 2
1 2

output

Yes

explanation

选出任意一条边都能满足条件。

样例二

input

2 3
1 2
1 2
1 2

output

No

explanation

无论怎么选择都会有一边存在环。

样例三

input

5 4
1 2
2 3
1 5
2 4

output

Yes

explanation

这张图本来就是森林,所以无论怎么选都是满足条件的。

样例四

input

5 8
1 2
2 3
3 1
1 4
4 5
5 1
2 4
3 5

output

Yes

explanation

选出边 $(1,2),(2,3),(1,4)$ 和 $(3,5)$ 是满足条件的。

样例五

input

5 9
1 2
2 3
3 1
1 4
4 5
5 1
2 4
3 5
2 5

output

No

样例六

见样例数据下载。

样例七

见样例数据下载。

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $3$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 $n$ 的规模 $m$ 的规模 其他
1$20$$n \leq 10$$m \leq 20$
2$20$$n \leq 300$$m \leq n+7$保证图联通
3$10$$m \leq 600$每个点的度数都不小于 $4$
4$30$
5$20$$n \leq 2000$$m \leq 4000$

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载

新年快乐!

2016,好好做人。