Background

"With sincere prayers."

"At the moment when the stars fall."

"Two figures are reflected in the water."

"Shining together."

Problem Description

Kuon wants a tree with as few nodes as possible.

She will assign each node a positive integer label, such that adjacent nodes have different labels and the sum of all node labels is minimized. If there are multiple valid assignments, she will choose any one of them.

Please help construct a tree such that, after Kuon finishes labeling it, the maximum label is guaranteed to be not less than $k$.

Input Format

Two integers $k$ and $x$, where $k$ is as described in the statement, and $x$ is the scoring parameter.

Output Format

The first line contains an integer $n$, the size of the tree you construct.

The next $n - 1$ lines each contain two integers $u, v$, representing an edge of your tree.

2 5

5
1 2
2 3
3 4
4 5

3 20

16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16

Hint

The scoring is as follows.

• If the constructed tree satisfies the requirements and $1 \le n \le x$, $1 \le u, v \le n$, then you will receive the full score for that test case.
• Otherwise, you will receive $0$ points for that test case.

For $100\%$ of the testdata, $1 \le k \le 12$, $1 \le x \le 10^6$. For each test point, there is guaranteed to be a construction that can achieve full score.

Translated by ChatGPT 5