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 branch hooks, which are connected using tree branches. The branch connects two distinct hooks and . 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:

for all

##### Subtask 1 [16%]

##### Subtask 2 [84%]

No additional constraints.

#### Input Specification

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

The next lines describe the Christmas tree's structure. Each line contains integers, and , indicating a connecting tree branch between the hooks and .

#### Output Specification

**This problem is graded with a custom checker.**

Output on the first line, describing the maximum number of tree branches **added** to the christmas tree.

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

If is maximized **and** the new edges form **any** valid cactus graph, you will receive of the points for that test case and a verdict of `Accepted`

. If only is correct, you will receive of the points for that test case and a verdict of `Partially Accepted`

. If 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:

- One branch between hooks and .
- One branch between hooks and .

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

## Comments