题目描述

你是否听说过 Just Odd Inventions 公司？该公司的业务是“进行各种奇妙的发明（just odd inventions）”，这里我们简称为 JOI 公司。

JOI 公司的某实验室中有一个复杂的电路，该电路由 $N$ 个节点和 $M$ 条细长的电阻组成。节点编号从 $1$ 到 $N$。每个节点可以被设置为“高电压”或“低电压”状态。每条电阻连接两个节点，当其中一个节点处于“高电压”、另一个节点处于“低电压”时，电流才会流过该电阻。如果两个节点都处于“高电压”或都处于“低电压”，则电流不会流过该电阻。

某日，JOI 公司为维护该电路，决定选择一条电阻，使其不导电，而其余 $M-1$ 条电阻均导电。为了满足这一条件，需要确定有多少条电阻可以被选为“不导电”的电阻。

另外，JOI 公司使用这个奇妙电路做出了何种发明，是公司内部最高机密，除了社长外无人知晓。

题目

给定电路的信息，编写一个程序，计算在维护时可以选为“不导电”的电阻的数量。

输入格式

从标准输入读取以下数据：

• 第一行包含两个整数 $N$、$M$，以空格分隔，表示有 $N$ 个节点、$M$ 条电阻。
• 接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含两个整数 $A_i$、$B_i$（满足 $1 \le A_i \le N$，$1 \le B_i \le N$，且 $A_i \ne B_i$），以空格分隔，表示第 $i$ 条电阻连接节点 $A_i$ 和节点 $B_i$。

输出格式

在标准输出中，输出一行，表示在维护时可以选为“不导电”的电阻的数量。

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

1

4 4
1 2
2 3
3 2
4 3

2

13 16
1 6
2 6
3 1
3 2
4 7
4 7
5 9
6 5
8 2
8 13
9 11
10 3
11 10
11 12
12 8
13 6

3

提示

样例 1 解释

在该示例中，仅能使第 3 条电阻不导电。例如，将节点 1 和节点 4 设置为“高电压”，将节点 2 和节点 3 设置为“低电压”即可。由于第 3 条电阻连接的是节点 1 和节点 4，因此电流不会流过该电阻。无法选择第 3 条电阻以外的任何电阻作为维护时不导电的电阻。

:::align{center} :::

样例 2 解释

在该示例中，可以选择第 1 条电阻或第 4 条电阻作为维护时不导电的电阻。

:::align{center} :::

数据范围

所有输入数据均满足以下条件：

• $2 \le N \le 100\,000$
• $1 \le M \le 200\,000$

子任务

子任务 1 [10 分]

满足以下条件：

• $N \le 1\,000$
• $M \le 2\,000$

子任务 2 [10 分]

• 任意两个节点之间，均可通过若干条相连的电阻到达。
• 满足 $M = N$

子任务 3 [35 分]

• 任意两个节点之间，均可通过若干条相连的电阻到达。
• 满足 $M \le N + 100$

子任务 4 [45 分]

无额外限制。

翻译由 Qwen3-235B 完成