小红开灯（五，hard）

题号：NC292799
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

（本题和easy难度的区别是需要输出小红操作的方案）
小红拿到了一棵树，树上的每个节点上有一盏灯，每盏灯初始全部为“开启”状态。

小红每次操作可以改变相邻两盏灯的状态（开启变关闭，关闭变开启），她希望不存在两盏相邻的灯同时开启，请你帮小红计算至少需要操作多少次，并给出小红的一个操作方案。

我们定义，树上两个灯相邻，当且仅当它们之间有一条边连接。

第一行输入一个正整数，代表树的节点数量。
接下来的行，每行输入两个正整数，代表节点和节点是相邻的。

第一行输出一个正整数，代表操作的最小次数。
接下来的行，每行输出两个正整数，代表同时对节点和节点进行操作。
请务必保证节点和节点有一条边连接。
如果存在多种方案，输出任意合法的均可。

示例1

复制

复制

1
4 1

操作1次后，1和4号节点的灯均被关闭，此时不存在两个相邻的灯同时开启。