← 返回题目列表

AtCoder · icpc2013spring_j

J. 树重建

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

问题陈述

你有一个有向图。 在图的每条边上分配一些非负值。 您知道图的值满足 流量守恒定律 也就是说,对于每个节点 v,传入的边上的值之和 v 等于 传出边的值之和 v。 例如,下面的有向图满足流守恒定律。

假设您选择图中的边子集,表示为 E', 然后擦除除边缘之外的所有值 E'。 现在您想通过仅查看剩余信息来恢复已删除的值。 由于流量守恒定律,有可能恢复所有被擦除的值。 您的任务是计算此类的最小可能尺寸 E'.

例如,最小子集 上图的 E' 在下图中将是绿色边缘。 通过流守恒定律,我们可以恢复灰度边缘上的值。


输入

输入由多个测试用例组成。 每个测试用例的格式如下。

N M
s_1 t_1
...
s_M t_M

第一行包含两个整数 N (1 \leq N \leq 500)和 M (0 \leq M \leq 3,000)分别表示节点和边的数量。 以下每一项 M 行由两个整数组成 s_i 和 t_i (1 \leq s_i, t_i \leq N)。这意味着有一个边缘 图中的 s_i to t_i 。

您可以假设给定的图很简单:

  • 没有自循环: s_i \neq t_i.
  • 没有多边:对于所有 i < j, \{s_i, t_i\} \neq \{s_j, t_j\}.

此外,还保证给定图的每个组件都是强连接的。 也就是说,对于每对节点 v 和 u,如果存在来自 v to u,则存在一条来自 u to v.

请注意,您不会获得边缘值的信息,因为它不会影响答案。

输出

对于每个测试用例,在一行中打印答案。

示例输入 1

9 13
1 2
1 3
2 9
3 4
3 5
3 6
4 9
5 7
6 7
6 8
7 9
8 9
9 1

样本输入 1 的输出

5

示例输入 2

7 9
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
7 1

样本输入 2 的输出

3

示例输入 3

4 4
1 2
2 1
3 4
4 3

样本输入 3 的输出

2