Optimal Cultural Tour Route

Mr. Malnar is visiting Seged, a city whose attractions are connected by a tree: there are \(n\) sights (numbered from 1 to n) connected by \(n-1\) bidirectional roads. Since there is a unique simple path between any two sights and each road takes exactly one minute to traverse, the distance between any two sights is well defined.

Malnar has a list of \(m\) restaurants he wishes to visit; the list consists of \(m\) positive integers where the \(i\)th integer is the sight near which the \(i\)th restaurant is located. Equally, he has a list of \(m\) dessert shops (each providing ice cream), given as \(m\) positive integers -- the \(i\)th number indicates the sight where the \(i\)th dessert shop is located.

There are two quirks in his itinerary:

• Immediately after dining at a restaurant, he must go to a dessert shop for ice cream.
• He refuses to visit the same dessert shop more than once.

Starting at sight 1 and ending at sight 1, Mr. Malnar wants to plan his tour such that he alternates between restaurant and dessert shop visits. In other words, his route is:

[ 1 \to R_{i_1} \to D_{j_1} \to R_{i_2} \to D_{j_2} \to \cdots \to R_{i_m} \to D_{j_m} \to 1, ]

where \(R_{i_k}\) and \(D_{j_k}\) are chosen (in a permutation) from the two lists. The total travel time is the sum of the distances along the unique paths in the tree:

[ \text{Cost} = d(1, R_{i_1}) + \sum_{k=1}^{m} d(R_{i_k}, D_{j_k}) + \sum_{k=1}^{m-1} d(D_{j_k}, R_{i_{k+1}}) + d(D_{j_m}, 1). ]

Your task is to compute the minimum total travel time as well as a valid visit order (i.e. the sequence of restaurants visited and the sequence of dessert shops visited) that achieves this minimum.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (2 \le n,\; 1 \le m \le \text{small})\), representing the number of sights and the number of restaurant/dessert shop pairs.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating that there is a bidirectional road between sights \(u\) and \(v\).

The next line contains \(m\) positive integers: the locations of the restaurants.

The next line contains \(m\) positive integers: the locations of the dessert shops.

outputFormat

Output three lines:

1. The first line contains the minimum total travel time (in minutes).
2. The second line contains \(m\) integers representing the order in which the restaurants are visited.
3. The third line contains \(m\) integers representing the order in which the dessert shops are visited.

sample

4 1
1 2
2 3
3 4
4
3

6
4
3

</p>