分数: 466 分
问题陈述
高桥是一所大学校园的网络管理员。校园有 N 建筑物和 M 走廊,每栋建筑的编号为 1 to N。的 i第走廊双向连接建筑物 u_i 和建筑 v_i.
该校园内的建筑分为“教育楼”和“研究楼”两种类型,每条走廊都连接着不同类型的建筑。换句话说,由建筑物和走廊组成的图是二分图。然而,输入中并未给出每栋建筑属于哪种类型。此外,该图不一定是连通的。
根据大学政策,所有走廊均应提供 Wi-Fi。当建筑物中安装了 Wi-Fi 接入点时,以该建筑物为端点的所有走廊都可以使用 Wi-Fi。
Takahashi 希望实现这样一种状态:对于每个走廊,其端点的两座建筑物中至少有一栋安装了接入点。求满足该条件需要选择的最少建筑物数量。
约束
- 1 \leq N \leq 10^5
- 0 \leq M \leq 10^5
- 1 \leq u_i, v_i \leq N
- u_i \neq v_i (无自环)
- 最多有一条走廊连接同一对建筑物(无多边)
- 给定的图是二分图
- 图不一定相连
- 所有输入值均为整数
输入
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
- 第一行包含建筑物数量 N 和走廊数量 M,用空格分隔。
- 的 i- 以下各项 M 行 (1 \leq i \leq M) 包含数字 由 u_i 和 v_i 连接的两座建筑物 i第一条走廊,间隔一个空格。
输出
在一行中打印出需要安装接入点以便在所有走廊上提供 Wi-Fi 的最少建筑物数量。
示例输入 1
4 4 1 2 2 3 3 4 4 1
示例输出 1
2
示例输入 2
5 4 1 2 1 3 1 4 1 5
示例输出 2
1
示例输入 3
10 8 1 6 1 7 2 7 2 8 3 8 3 9 4 9 5 10
示例输出 3
5
示例输入 4
8 16 1 5 1 6 1 7 1 8 2 5 2 6 2 7 2 8 3 5 3 6 3 7 3 8 4 5 4 6 4 7 4 8
示例输出 4
4
示例输入 5
1 0
示例输出 5
0