401377: GYM100425 F Mexico

Mexico is one of the most interesting countries for tourists. Endless sandy beaches, unique culture, ancient Indian temples... Beautiful nature: tropical forests, mountains, deserts... And, of course, cacti!

A certain tourist arrived in Mexico and decided to explore the country. For this, he rented a car and made a plan for visiting the cities of the country on K days ahead.

We know that in Mexico, there are N towns connected by M roads. Each road connects two different cities, and no two roads connect the same pair of cities. All roads have the same length and are bidirectional, and it is possible to travel by road network from each city to any other.

In addition, if you look at a road network of Mexico as a graph where vertices are cities and roads are edges, this graph will be a vertex cactus: a connected undirected graph in which each vertex belongs to at most one simple cycle.

The tourist begins his journey through the cities of Mexico in city 0. Following the plan, on each day, he chooses a city for the excursion and drives to it from the city in which he was the previous day by the shortest route. If the city does not change, the tourist continues the excursion in the current city.

Each time when the tourist is driving somewhere, he should refuel the car in the city that is closest to the middle of his path. If there are several such cities, any of them can be selected.

Given the road map of Mexico and the numbers of cities that tourist plans to explore, determine the cities, in which he will refuel his car.

The first line of the input contains two integers: the number of cities N (1 ≤ N ≤ 10⁵) and the number of roads M.

Each of the next M lines describes one road and contains two integers U_i and V_i (0 ≤ U_i, V_i ≤ N - 1) which are the cities connected by i-th road.

The next line contains an integer K (1 ≤ K ≤ 10⁵) which is the number of cities which the tourist plans to visit.

The next line contains K integers: the numbers of these cities in the order in which he plans to visit them.

Print K integers: the numbers of cities in which the tourist will refuel his car, listed in the order of refueling events. In case there are several solutions, print any of them.

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

4 2 0 3 4