The WAC team is setting up a Christmas tree! However, the usual Christmas tree's design has become monotonous to them. They need something new and different!

Why not use a cactus instead?

You have been assigned the job of transforming the tree into a cactus. A cactus is a connected graph where every edge belongs to at most one cycle. In addition, the graph may not contain self loops or parallel edges.

The Christmas tree currently has ~N~ branch hooks, which are connected using ~N-1~ tree branches. The ~i^\text{th}~ branch connects two distinct hooks ~a_i~ and ~b_i~. You are allowed to add some new tree branches, each connecting two separate hooks.

To make sure you're not slacking off on your task, the WAC team requires you to add as many new tree branches to the cactus as possible. Please determine the maximum number of tree branches you'll need to add, and tell the WAC team where to add each branch!

For this problem, Python users are recommended to use CPython over PyPy.

Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N \le 200\,000~
~1 \le a_i, b_i \le N~ for all ~1 \le i \le N-1~

Subtask 1 [16%]

~1 \le N \le 8~

Subtask 2 [84%]

No additional constraints.

Input Specification

The first line will contain an integer ~N~, the number of tree hooks on the Christmas tree.

The next ~N-1~ lines describe the Christmas tree's structure. Each line will contain ~2~ integers, ~a_i~ and ~b_i~, indicating a connecting tree branch between the hooks ~a_i~ and ~b_i~.

Output Specification

This problem is graded with a custom checker.

Output ~K~ on the first line, describing the maximum number of tree branches added to the Christmas tree.

Next, output ~K~ lines after the first line, describing the newly added edges. Each line should contain ~2~ integers, ~a_i~ and ~b_i~, indicating a new connecting tree branch between the hooks ~a_i~ and ~b_i~.

If ~K~ is maximized and the ~K~ new edges form any valid cactus graph, you will receive ~100\%~ of the points for that test case and a verdict of Accepted. If only ~K~ is correct, you will receive ~25\%~ of the points for that test case and a verdict of Partially Accepted. If ~K~ is incorrect, you will receive a verdict of Wrong Answer and no additional test cases will be executed for that subtask. The judge will also provide feedback with your verdict for each test case.

Your points for a subtask is equal to the minimum number of points achieved in each test case of that subtask.

Sample Input

6
6 4
3 1
3 6
4 5
2 3

Sample Output

2
2 1
3 5

Sample Explanation

Two new tree branches can be added to the Christmas tree:

1. One branch between hooks ~2~ and ~1~.
2. One branch between hooks ~3~ and ~5~.

This is one of the several valid set of branches you can add to the tree.