Redpanda

题目描述

在喜马拉雅的一片森林里，一只小熊猫需要爬上一棵很高的树。可惜它恐高，不敢爬到超过第 $K$ 层的位置。于是它希望你帮它想办法，把这棵树改造成“不那么高”的树。

给定一棵以节点 $1$ 为根的树。根节点位于第 $1$ 层，根的儿子位于第 $2$ 层，以此类推。

你可以进行若干次操作。一次操作由两个步骤组成：

1. 删除当前树中的任意一条边；
2. 添加一条新的边。

任务

求最少需要多少次操作，才能把给定树变成一棵所有节点层数都不超过 $K$ 的树。

同时需要输出这些操作的具体方案。

输入格式

第一行包含两个整数 $N,K$，分别表示节点数和最终允许的最大层数。

接下来 $N-1$ 行，每行包含两个整数 $X,Y$，表示树中有一条连接 $X$ 和 $Y$ 的边。

输出格式

第一行输出一个整数 $S$，表示最少操作次数。

接下来 $S$ 行，每行输出四个整数：

A B C D

表示本次操作为：

• 删除边 $(A,B)$；
• 添加边 $(C,D)$。

输出的操作必须满足：

• 删除的边在当前图中必须存在；
• 添加的边在当前图中不能已经存在；
• 不能添加自环；
• 所有操作结束后，得到的图必须是一棵树；
• 在第一步操作之后、最后一步操作之前，中间状态允许暂时不是树。

数据范围

• $2\le N\le 300\,000$；
• $2\le K\le N$；
• 输入边满足 $1\le X,Y\le N$；
• 输出操作中的点编号满足 $1\le A,B,C,D\le N$。

子任务

样例

输入

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

输出

1
3 4 6 1

样例解释

删除边 $(3,4)$，并添加边 $(6,1)$。最终所有节点的层数都不超过 $4$。