Problem Background

Source: Eight Immortals Offering Wine, clickable.

• Lu Dongbin — Drunkenly Lifting the Kettle with Mighty Strength;
• Tie Guaili — Spinning Elbows and Knees, Drunk and True;
• Han Zhongli — Stumbling Forward with Kettle, Directly to the Heart;
• Lan Caihe — Offering Wine with a Single Hand, Breaking the Waist;
• Zhang Guolao — Drunkenly Throwing Cups, Kicking in Succession;
• Cao Guojiu — Immortal Offering Wine, Throat Lock;
• Han Xiangzi — Gripping Wrist, Punching Chest, Drunkly Playing the Flute;
• He Xiangu — Twisting Waist, Offering Wine, Drunkenly Dancing Steps.

Problem Description

Given a tree \( T \) with \( n \) nodes, where each node is connected to no more than 2 other nodes.

We perform the following operations sequentially on nodes \( u = 1 \sim n \):

• Randomly select an integer \( x (\ge k) \);
• Create \( x \) new nodes, each connected to node \( u \).

Clearly, after these operations, the resulting structure is still a tree \( T' \), with \( m = n + \sum x \) nodes.

Given the post-operation tree \( T' \) and its node count \( m \), reconstruct the original tree \( T \). If there are multiple solutions, output any one that maximizes \( n \).

It is important to note that during reconstruction and output, we are only concerned with the shape of the tree, not the relative numbering of the nodes.

Input Format

The first line contains two positive integers \( m \) and \( k \), representing the number of nodes in tree \( T' \) and the lower bound of the random number \( x \), respectively.

Lines 2 to \( m \) each contain two positive integers \( u \) and \( v \), representing an edge in tree \( T' \).

Output Format

The first line contains a positive integer \( n \), representing the number of nodes in the constructed tree \( T \).

Lines 2 to \( n \) each contain two positive integers \( u \) and \( v \), representing an edge in tree \( T \).

The output must ensure \( 1 \le u, v \le n \).

Sample Input and Output

Input Sample #1

5 1
1 2
1 3
1 4
1 5

Output Sample #1

1

Input Sample #2

7 0
1 2
1 3
1 4
1 5
1 6
1 7

Output Sample #2

3
1 2
1 3

Input Sample #3

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

Output Sample #3

3
1 2
2 3

Notes

Sample Explanation

In Sample #1, only node 1 could be in tree \( T \): it corresponds to \( x = 4 \).

In Sample #2, nodes 1, 2, and 3 are in tree \( T \): node 1 corresponds to \( x = 4 \), and nodes 2, 3 correspond to \( x = 0 \).

In Sample #3, nodes 1, 2, and 3 are in tree \( T \): they all correspond to \( x = 2 \).

Sample #3 provides a diagram where red nodes represent nodes in tree \( T \), and all nodes are in tree \( T' \).

Data Range

Note: Subtask 4 is a non-scored Hack data, and only passing all Subtasks 1 through 4 counts as AC.

For 100% of the data: \( 1 \le m \le 10^5, k \in [0, m) \), the input guarantees a solution.

见题面 Input 部分

见题面 Output 部分