← 返回题目列表

Codeforces · 771/A

A. 熊和友谊条件

中文机器翻译题面 查看原题

Bear Limak 检查社交网络。它的主要功能是两个成员可以成为朋友(然后他们可以互相交谈并分享有趣的图片)。

有 n 个成员,编号为 1 到 n。 m 对成员是朋友。当然,会员不能和自己成为朋友。

设 A-B 表示成员 A 和 B 是朋友。 Limak 认为,当且仅当满足以下条件时,网络才是合理的:对于每三个不同的成员(X、Y、Z),如果 X-Y 和 Y-Z,则也是 X-Z。

例如:如果 Alan 和 Bob 是朋友,Bob 和 Ciri 是朋友,那么 Alan 和 Ciri 也应该是朋友。

你能帮助Limak检查一下网络是否合理吗?相应地打印“是”或“否”,不带引号。

输入

输入的第一行包含两个整数 n 和 m (3 ≤ n ≤ 150 000, $$0 \leq m \leq min(150\ 000, \frac{n \cdot (n-1)}{2})$$) — 成员数量和好友成员对数量。

接下来 m 行的第 i 行包含两个不同的整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。成员ai和bi是朋友。任何一对成员都不会在输入中出现多次。

输出

如果给定的网络合理,则在单行中打印“YES”(不带引号)。否则,在一行中打印“NO”(不带引号)。

示例

输入 #1

4 3
1 3
3 4
1 4

输出 #1

YES

输入 #2

4 4
3 1
2 3
3 4
1 2

输出 #2

NO

输入 #3

10 4
4 3
5 10
8 9
1 2

输出 #3

YES

输入#4

3 2
1 2
2 3

输出#4

NO

注意

下图显示了第一个样本(左侧)和第二个样本(右侧)的情况。每条边代表两个作为朋友的成员。在第二个样本中,答案为“否”,因为成员 (2, 3) 是朋友,成员 (3, 4) 是朋友,而成员 (2, 4) 不是朋友。