#264. 社交网络

社交网络

强哥最近沉迷于社交网络,他想研究自己在不同社交圈中的互动情况。他将自己所有的社交关系整理成一张图:

  • nn 个社交圈成员(包括强哥自己)。
  • mm 条关系,表示某两人是好友。
  • ii 条好友关系连接成员 uiu_iviv_i
  • 如果两条关系 (ui,vi)(u_i, v_i)(uj,vj)(u_j, v_j) 是同一条,说明强哥手抖重复记录时仅当 i=ji = j(即社交关系图不存在重边)。

强哥的目标是检查他所在的每一个社交圈(连通块),看是否符合以下条件: “每个社交圈的成员数与好友关系数相等。”

数据范围

  • 1N2×1051 \leq N \leq 2 \times 10^5(成员数量)
  • 0M2×1050 \leq M \leq 2 \times 10^5(好友关系数量)
  • 1uiviN1 \leq u_i \leq v_i \leq N(好友关系编号)
  • 所有输入均为整数。

输入格式

输入通过标准输入,格式如下:

N M
u_1 v_1
u_2 v_2
...
u_M v_M

输出格式

如果强哥的所有社交圈都满足条件,输出:

Yes

否则,输出:

No

示例

输入样例 1

3 3
2 3
1 1
2 3

输出样例 1

Yes

解释: 强哥的社交网络有两个连通块:

  1. 一个仅由成员 11 组成,包含 11 条好友关系(111 \leftrightarrow 1)。
  2. 一个由成员 2,32, 3 组成,包含 22 条好友关系(232 \leftrightarrow 3232 \leftrightarrow 3)。 两个连通块都满足成员数等于关系数。

输入样例 2

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

输出样例 2

Yes

解释: 强哥的社交网络是一个整体连通块,包含 55 名成员和 55 条好友关系,满足条件。