← 返回题目列表

AtCoder · typical90_bz

078. 简单的图问题(★2)

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

配点:2 点

問題文

N 頂点 M 给出了一个带有连接边的简单无向图。图的每个顶点都有 它们的编号最大为 1 减去 N 编号至 i 第几条边是边界 a_i 和 按字典顺序比较 b_i 双向连接。

请输出满足以下条件的顶点数。

  • 顶点数低于其自身的相邻顶点恰好是 1 有

制約

  • 2 \leq N \leq 100000
  • N - 1 \leq M \leq \mathrm{min}(\frac{N(N - 1)}{2}, 100000)
  • 1 \leq a_i, b_i \leq N
  • 给定的图是一个简单的图
  • 给定的图形已连接
  • 所有输入均以整数形式给出

入力

输入是按以下格式从标准输入给出的。

N M
a_1 b_1
\vdots
a_{M} b_{M}

出力

请在一行中输出符合条件的顶点的个数。


入力例 1

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

出力例 1

3

符合条件的顶点2, 4, 5 可以得到第 3 一。 请注意,无法创建

  • 頂点 2 作为比自身顶点编号小的邻接顶点,顶点 1 满足
  • 頂点 4 作为比自身顶点编号小的邻接顶点,顶点 2 满足
  • 頂点 5 作为比自身顶点编号小的邻接顶点,顶点 2 满足

入力例 2

2 1
1 2

出力例 2

1

条件的顶点 在 2 。


入力例 3

7 18
7 2
1 6
5 2
1 3
7 6
5 3
5 6
5 4
1 7
2 6
3 4
5 1
4 7
4 6
5 7
3 2
4 2
1 4

出力例 3

0