Restoring the Original Tree

You are given a tree \(T'\) with \(m\) nodes obtained by the following procedure from an original tree \(T\) on \(n\) nodes:

• The original tree \(T\) is a tree in which every vertex has at most 2 neighbors (that is, \(T\) is a path).
• For every vertex \(u\) of \(T\) (with \(u=1,2,\ldots,n\)), a random integer \(x\) (with \(x\ge k\)) is chosen, and \(x\) new vertices are created. An edge is added between each of these new vertices and \(u\).

Thus, the resulting tree \(T'\) has \(m = n + \sum_{u=1}^{n} x_u\) nodes. You are given \(T'\) (by its edges) and the number \(m\). Your task is to restore an original tree \(T\) (i.e. its structure) from \(T'\). If there are multiple answers, output any one that maximizes \(n\) (the number of nodes in the original tree).

Note: When restoring and outputting \(T\), you only need to care about the tree structure (i.e. the connectivity); the vertex labels can be reassigned arbitrarily.

Constraints and remarks: In the procedure, the added number \(x\) for each vertex always satisfies \(x \ge k\). In an original tree \(T\) that is a path, if \(T\) has:

• Exactly one vertex (\(n=1\)): the only vertex must have degree at least \(k\) in \(T'\).
• If \(n \ge 2\): an endpoint \(u\) in \(T\) has one adjacent original vertex, so its degree in \(T'\) is \(x+1\) and must satisfy \(x+1 \ge k+1\); an internal vertex has two adjacent original vertices, so its degree in \(T'\) is \(x+2\) and must satisfy \(x+2 \ge k+2\).

Your goal is to extract a path (chain) from \(T'\) satisfying these conditions with the maximum possible number of vertices.

inputFormat

The first line contains two integers \(m\) and \(k\), where \(m\) is the number of vertices in \(T'\) and \(k\) is the parameter used in the construction.

If \(m \ge 2\), each of the next \(m-1\) lines contains two integers \(u\) and \(v\) representing an edge in \(T'\). It is guaranteed that \(T'\) is a tree.

outputFormat

First, output an integer \(n\) denoting the number of vertices in the restored original tree \(T\) (the maximum possible value of \(n\)).

If \(n \ge 2\), then output \(n-1\) lines each containing two integers representing an edge of \(T\). The vertices can be labeled arbitrarily from \(1\) to \(n\) and the order of edges does not matter.

sample

1 1

1