P12504 「ROI 2025 Day1」树上的青蛙

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day1 T4.** ***[Лягушки на дереве](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day1.pdf)*** 在天狼星物理技术学院，你不仅能看到普通的青蛙，还能遇见会变色的树蛙！这些神奇的小家伙可以从绿色变成棕色，或者从棕色变回绿色，简直就像自然界的魔术师。 所谓树，是一个没有环的连通图。树上的每个节点都住着一只青蛙，初始时它们全是绿色的。青蛙们喜欢在树上跳来跳去，每次跳跃会从当前节点沿着边跳到旁边的节点。每跳一次，它们的颜色就会切换到相反的颜色。 青蛙们最爱成双成对地唱歌，但每一对必须由一只绿色和一只棕色的青蛙组成。为了组成一对，某只青蛙需要跳到另一只青蛙所在的节点，且跳跃次数不能超过 $d$ 次。为了保证到达时颜色与对方不同，跳跃次数必须是奇数。 你的任务是找出最多能组成多少对青蛙合唱团。每只青蛙只能加入一对。如果能正确计算出最多的合唱团数量，你就能为子任务拿到部分分数。要想拿满分，你还得指出哪些青蛙应该配对，才能达到这个最大数量。

第一行包含一个整数 $n$ $(2 \leq n \leq 5 \cdot 10^5)$，表示树上的节点数量。 第二行包含一个奇数 $d$ $(1 \leq d \leq n - 1)$，表示一只青蛙前往另一只青蛙所在节点的最大跳跃次数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ $(1 \leq u, v \leq n)$，表示树上两个通过一条边连接的节点。节点编号从 $1$ 到 $n$。

第一行输出一个整数 $m$，表示最多能组成的青蛙合唱团数量。 如果你不想提供具体的配对方案，第二行输出 $-1$，然后结束程序。 否则，在接下来的 $m$ 行中，每行输出两个整数 $u_i$ 和 $v_i$，表示一对青蛙所在的节点编号，它们将在其中一个节点相遇并组成合唱团，需满足上述规则。 如果有多种方式可以达到最大合唱团数量，输出任意一种即可。

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $6$ | $n \le 14$ | $0$ | | $2$ | $6$ | $n \le 300\,000$，$d = n-1$ | | $3$ | $10$ | $n \le 300\,000$，$d = 1$ | | $4$ | $14$ | $n \le 300\,000$，$d = 3$ | | $5$ | $8$ | $n \le 200$ | | $6$ | $12$ | $n \le 30\,000$，$d \le 9$ | | $7$ | $4$ | $n \le 300\,000$，$d \le 13$ | | $8$ | $10$ | $n \le 300\,000$，$d \le 99$ | | $9$ | $14$ | $n \le 300\,000$ | | $10$ | $16$ | 无附加限制 |