问题陈述
你有一个有向图。 在图的每条边上分配一些非负值。 您知道图的值满足 流量守恒定律 也就是说,对于每个节点 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