← 返回题目列表

AtCoder · awc0071_e

E. Wi-Fi 接入点的安装

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

分数: 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