Invasion of the Tree-like Supercomputer

After a legendary incident that increased the population of the Worm Nation by millions (or "Worm mouths"?), the nation has become ever more prosperous. Recently, mysterious sheets of paper were found underground – they turned out to be the design blueprints of the supercomputer from City X in country D!

This supercomputer, named "Tree", consists of \(n\) computing nodes connected by \(n-1\) bidirectional cables, where each node is numbered with a positive integer not exceeding \(n\). As the name suggests, these nodes and cables form a tree structure.

The Worm King has the complete information of the tree including \(n\) and the connections of the \(n-1\) cables. He now orders the two most powerful hackers of the nation, Little P and Little H, to infiltrate and destroy the supercomputer as much as possible.

The plan is as follows:

1. Little P chooses a computing node as his starting point and marks it with a P.
2. He may then repeatedly (possibly zero times) perform the following move: from his current node, he chooses an unmarked cable, moves to the cable's other end, and marks both the cable he passes and the destination node with a P.
3. Afterwards, Little H picks a computing node as her starting point and marks it with a H.
4. Then, she may repeatedly (possibly zero times) perform a similar move: from her current node, she chooses an unmarked cable, moves to its other end, and marks both the cable and the destination node with an H. (Note that Little H cannot travel along a cable that has already been marked with a P, although she may pass through nodes that were marked with P.)
5. After both hackers have executed their moves, all nodes and cables that have been marked (either with P or H) are deleted.
6. Then, for every remaining cable, if one or both of its endpoints were deleted in the previous step, that cable is also deleted.

The remaining structure consists of several connected components (possibly zero). In order to cause maximum damage, the Worm King desires the number of connected components to be as large as possible. He has turned to you for help.

However, the hackers might already have some parts of an optimal plan computed. You will be given an integer \(x\) with the following meaning:

• If \(x=0\): Neither hacker has computed any part of an optimal strategy. You must determine both Little P's and Little H's invasion routes.
• If \(x=1\): Little P has fixed his route. In his plan, he starts at node \(p_0\) and goes to node \(p_1\) (and then stops). You only need to determine Little H's invasion route.
• If \(x=2\): Both hackers have agreed on an optimal plan. Little P goes from \(p_0\) to \(p_1\) and stops, and Little H goes from \(h_0\) to \(h_1\) and stops. In this case, you only need to calculate the final number of connected components after the deletion process.
</p>

Note: It is allowed for a hacker to make 0 moves (i.e. just choose a starting node). The final remaining graph is the subgraph induced by the nodes not visited by either hacker.

inputFormat

The input begins with a line containing two integers \(n\) and \(x\) where \(1 \le n \le 10^5\) and \(x \in \{0,1,2\}\). The next \(n-1\) lines each contain two integers \(u\) and \(v\) denoting an undirected cable connecting nodes \(u\) and \(v\).

Depending on the value of \(x\), additional input is provided:

• If \(x = 1\), one more line follows containing two integers \(p_0\) and \(p_1\) representing Little P's predetermined invasion route.
• If \(x = 2\), one more line follows containing four integers \(p_0\), \(p_1\), \(h_0\), and \(h_1\) representing Little P's and Little H's predetermined invasion routes, respectively.
• If \(x = 0\), no extra lines are given.

It is guaranteed that the given edges form a tree.

outputFormat

If \(x = 0\): Output two lines. The first line is Little P's invasion route (a space-separated sequence of node numbers) and the second line is Little H's invasion route.

If \(x = 1\): Output one line containing Little H's invasion route (a space-separated sequence of node numbers).

If \(x = 2\): Output a single integer representing the number of connected components remaining after the deletion process.

sample

1 0

1
1

</p>