题目描述

译自 ROI 2025 Day1 T4. Лягушки на дереве

在天狼星物理技术学院，你不仅能看到普通的青蛙，还能遇见会变色的树蛙！这些神奇的小家伙可以从绿色变成棕色，或者从棕色变回绿色，简直就像自然界的魔术师。

所谓树，是一个没有环的连通图。树上的每个节点都住着一只青蛙，初始时它们全是绿色的。青蛙们喜欢在树上跳来跳去，每次跳跃会从当前节点沿着边跳到旁边的节点。每跳一次，它们的颜色就会切换到相反的颜色。

青蛙们最爱成双成对地唱歌，但每一对必须由一只绿色和一只棕色的青蛙组成。为了组成一对，某只青蛙需要跳到另一只青蛙所在的节点，且跳跃次数不能超过 $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$，表示一对青蛙所在的节点编号，它们将在其中一个节点相遇并组成合唱团，需满足上述规则。

如果有多种方式可以达到最大合唱团数量，输出任意一种即可。

8
7
1 2
2 3
3 4
3 5
1 6
6 7
3 8

3
2 7
6 3
4 1

11
3
1 2
2 3
3 4
3 5
3 6
3 7
1 8
8 9
8 10
8 11

4
3 7
11 8
10 2
1 6

提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。