Ties and the Safe Heist

You have hired an assistant with the profits from your sales robot. Now you are ready to break into the safe that holds the CEOI medals. The safe is hidden in one of the n rooms in a university building. The rooms are connected by n-1 doors such that the building forms a tree – i.e. every room can reach any other room and each room is connected with at most 3 doors.

Your assistant and you both have a floor‐plan of how the rooms are connected. However, the numbering of rooms and doors on your map may be different from those on your assistant’s map although they describe the same structure.

On the second day of the contest, while the judges are busy, your assistant will search the entire building. Once he finds the room containing the safe, he will leave you a hint leading to that room. Because you cannot bring your phone into the contest hall, he uses a nearly endless supply of identical ties (borrowed from last year’s BOI) to leave a message. In every room he visits he leaves some number of ties. When you later revisit the building, the only information available to you will be the number of ties in each room. Since too many ties in one room might be suspicious, you want to minimize the maximum tie count in any room.

Finally, while you sneak out (for example, during a bathroom break), you must follow the ties to the safe. The safe is hidden inside a room and you must uniquely identify it by its tie count. Moreover, you cannot waste time – you are allowed to go through at most d+30 doors, where d is the number of doors on the shortest path from your starting room to the safe room. Note that if you pass through the same door more than once, each passage counts.

Your task is to compute two things:

1. A tie distribution for the assistant, that is, how many ties to leave in each room of his map. To keep the hint as subtle as possible, you want to minimize the maximum number of ties in any room. (A simple optimal solution is to put 1 tie in the safe room and 0 in all others.)
2. A path in your map from your starting room to the safe room (which is the room corresponding to the safe room in the assistant’s map) that uses at most d+30 door passages, where d is the number of doors in the shortest path.

Important: Although both you and your assistant have the same building layout, the numbering of rooms in the two maps may be different. However, the maps are isomorphic (i.e. there exists a one‐to‐one correspondence between the rooms preserving connectivity). You are given both maps. The safe room is marked in the assistant’s map. You must determine the corresponding safe room in your map and compute a shortest path from your given start room to that room.

Note on correctness: Your solution must output a tie distribution (one integer per room in the assistant’s map) and a valid path (list of room numbers in your map) for every valid input. The tie distribution should be such that the maximum tie count is minimized. The straightforward solution of leaving 1 tie in the safe room and 0 in all other rooms is acceptable.

Input formulas:
The building has n rooms. In the assistant's map, the safe room is given as s and in your map the starting room is given as t. The two trees are isomorphic. The tree‐isomorphism condition means that if you root the trees at the safe room and the corresponding room, their AHU canonical forms will be identical. In particular, using the AHU algorithm, the canonical representation of a rooted tree is defined as:

\(\mathrm{AHU}(u)= ( \; \text{sort}_{v\in\text{children}(u)}\,\mathrm{AHU}(v)\;)\)

You can use this property to determine the correspondence.

inputFormat

The input is given as follows:

1. The first line contains a single integer n (the number of rooms).
2. The next n-1 lines each contain two integers u and v, indicating that room u and room v are connected by a door in the assistant’s map.
3. The next line contains an integer s, the safe room in the assistant’s map.
4. The following n-1 lines each contain two integers u and v, indicating that room u and room v are connected by a door in your map.
5. The last line contains an integer t, your starting room in your map.

outputFormat

Output two lines:

1. The first line contains n integers. The i-th integer is the number of ties to leave in room i of the assistant’s map. In an optimal solution, you can simply place 1 tie in the safe room and 0 in every other room.
2. The second line contains the sequence of room numbers (space-separated) representing a shortest path in your map from your starting room t to the corresponding safe room. This path will have length d (and is acceptable since d \(\leq d+30\)).

sample

3
1 2
2 3
2
1 3
2 3
2

0 1 0
2 3 1

</p>