#216010. [JOI Final 2026] 集邮 5 / Collecting Stamps 5

由于评测机性能差异，添加了额外 1.5 秒的时限。

JOI 君居住的 IOI 王国有 座城镇，编号从 到 。此外，IOI 王国有 条道路，编号从 到 。道路 () 双向连接城镇 和城镇 。通过使用若干条道路，可以从任何城镇前往任何其他城镇。

现在 IOI 王国将举办一场盖章拉力赛。每座城镇都将设置一个盖章站。城镇 () 的盖章站将在时间 设置。

JOI 君决定参加这场盖章拉力赛。在时间 ，JOI 君从其中一座城镇出发。此外，JOI 君在时间 拥有耐力值 。

当 JOI 君在时间 位于城镇 时，他采取以下行动：

1. 首先，如果当前城镇已经设置了盖章站，他就盖章。也就是说，如果 ，他就盖章。

2. 接下来，他选择结束盖章拉力赛或移动到另一座城镇。然而，只有当存在通过道路与城镇 相连且他尚未访问过的相邻城镇，并且他当前的耐力值至少为 时，他才能选择移动到另一座城镇。

3. 如果 JOI 君选择移动到另一座城镇，他会在与城镇 相连的城镇中选择一座未访问过的城镇 并移动到那里。他的耐力值减少 ，并于时间 到达城镇 。

4. 如果 JOI 君选择结束盖章拉力赛，若到那时为止他已经盖了至少一次章，则拉力赛成功，他可以在那里领取一份礼物。否则，拉力赛失败。

假设除城镇间的旅行时间外，所有其他时间都忽略不计。请注意，JOI 君不能留在同一座城镇。

你是活动组织者。如果 JOI 君在盖章拉力赛中取得成功，你需要在相应的城镇准备礼物。然而，礼物的数量是有限的，所以你想在尽可能少的城镇准备礼物。不幸的是，你不知道 JOI 君会从哪座城镇出发。因此，对于每个 ()，你想找出当 JOI 君从城镇 出发时，必须准备礼物的城镇数量。换句话说，你需要统计满足以下条件的 () 的数量：当 JOI 君在城镇 结束时，盖章拉力赛有可能成功。

给定关于 IOI 王国城镇和道路的信息、JOI 君的耐力值以及盖章站的设置时间，编写一个程序，对于每座城镇，计算当 JOI 君从该城镇出发时必须准备礼物的城镇数量。

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

输出 行到标准输出。第 行 () 应包含当 JOI 君从城镇 出发时必须准备礼物的城镇数量。

样例输入 1

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

样例输出 1

2
3
4
2
2

样例输入 2

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

样例输出 2

2
1
2
0
1

样例输入 3

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

样例输出 3

2
2
7
5
1
2
5

样例 1

我们展示一个当 时 JOI 君行动的例子。

• 在时间 ，JOI 君在城镇 并采取以下行动。
  • 城镇 的盖章站尚未设置，所以 JOI 君没有盖章。
  • JOI 君当前的耐力值是 。他移动到城镇 ，这是通过道路与城镇 相连的未访问城镇之一。
  • JOI 君的耐力值减少 ，并于时间 到达城镇 。
• 在时间 ，JOI 君在城镇 并采取以下行动。
  • 城镇 的盖章站尚未设置，所以 JOI 君没有盖章。
  • JOI 君当前的耐力值是 。他移动到城镇 ，这是通过道路与城镇 相连的未访问城镇之一。
  • JOI 君的耐力值减少 ，并于时间 到达城镇 。
• 在时间 ，JOI 君在城镇 并采取以下行动。
  • 城镇 的盖章站已经设置，所以 JOI 君盖章。
  • JOI 君选择在这里结束盖章拉力赛。由于他已经盖了至少一次章，盖章拉力赛成功。他收到一份礼物。

因此，当 JOI 君从城镇 出发并在城镇 结束盖章拉力赛时，盖章拉力赛可以成功，因此有必要在城镇 准备礼物。当 JOI 君从城镇 出发时，仅需在城镇 和 准备礼物，因此输出的第一行应为 。

此外，当 JOI 君从城镇 出发时，仅需在城镇 和 准备礼物，因此输出的第二行应为 。

该输入样例满足子任务 的限制。

样例 2

该输入样例满足子任务 的限制。

样例 3

该输入样例满足子任务 的限制。

限制

• 。
• 。
• ()。
• ()。
• 通过使用若干条道路，可以从任何城镇前往任何其他城镇。
• 给定的值均为整数。

子任务

1. (3 分) 。
2. (7 分) ()。
3. (10 分) 。
4. (11 分) ()。
5. (41 分) 。
6. (28 分) 无额外限制。