#214911. [JOI 2026 二次预选] 比太郎之旅 3 / Bitaro's Travel 3

JOI 国由 个城市和连接它们的 条道路构成。城市被编号为 到 ，道路被编号为 到 。道路 双向连接城市 和城市 。这里，。此外，对于任意两个城市的配对，连接它们的道路最多只有 条。也就是说， 或 。

比太郎现在在城市 ，正在制定旅行计划。旅行计划用数列 表示，它表示比太郎将访问的城市编号的顺序。这里， 是由 以上 以下的整数组成的、长度至少为 的数列。由于比太郎对旅行中访问城市编号的顺序有很强的执念，数列 在其长度为 时，必须满足以下所有条件。

1. 。
2. 对于各个 ，城市 与城市 由道路连接。
3. 对于各个 ，当 为奇数时有 成立，当 为偶数时有 成立。

例如， 和 满足第 个条件，但 不满足第 个条件。

比太郎想知道：无论制定怎样的旅行计划都无法到达的城市，即在满足上述所有条件的任意数列 中都不会出现其编号的城市，总共有多少个。

由于你不知道比太郎当前在什么城市，因此希望对 各自，计算比太郎问题的答案。

给定关于 JOI 国的城市与道路的信息，请编写程序，对 各自，求出无论比太郎制定怎样的旅行计划都无法到达的城市个数。

输入按以下格式给出。

输出 行。第 行输出当 时，无论比太郎制定怎样的旅行计划都无法到达的城市个数。

样例输入 1

4 4
1 2
1 3
1 4
3 4

样例输出 1

0
3
0
3

样例输入 2

2 0

样例输出 2

1
1

样例输入 3

4 3
1 3
3 4
2 4

样例输出 3

2
1
1
3

样例输入 4

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

样例输出 4

1
1
3
5
3
5

样例解释

样例 解释

当 时，作为 可能的数列有 、、、、 等。不存在无论制定怎样的旅行计划都无法到达的城市。

当 时，作为 可能的数列只有 。无论制定怎样的旅行计划，都无法到达城市 。

当 时，作为 可能的数列有 、 等。不存在无论制定怎样的旅行计划都无法到达的城市。

当 时，作为 可能的数列只有 。无论制定怎样的旅行计划，都无法到达城市 。

该输入示例满足子任务 的约束。

样例 解释

当 时，作为 可能的数列只有 。无论制定怎样的旅行计划，都无法到达城市 。

当 时，作为 可能的数列只有 。无论制定怎样的旅行计划，都无法到达城市 。

该输入示例满足子任务 的约束。

样例 解释

该输入示例满足所有子任务的约束。

样例 解释

该输入示例满足子任务 的约束。

约束

• 。
• 。
• 。
• 或 。
• 输入的值全部为整数。

子任务

• （12 分），。另外，存在一个将 重新排列得到的某个排列 ，并且对各个 ，存在一条连接 与 的道路。
• （19 分），。
• （15 分）。另外，存在一个将 重新排列得到的某个排列 ，并且对各个 ，存在一条连接 与 的道路。
• （17 分）对每个城市，与该城市直接由道路连接的城市最多为 个。
• （37 分）没有额外约束。