Treeland Security Agency (TSA) is a secret organization supposed to maintain the security in N cities of Treeland, which are identified by the numbers from 1 to N. The city with identifier 1 is the headquarters of TSA. For the safety of all agents working for TSA, to move from one city to another city one must follow a designated two-way road system which has a tree structure rooted at the headquarters. For every mission of TSA, two secret agents located in two different cities are assigned. After completing the mission, they have to gather at a designated city, called rendezvous, and travel together to the headquarters. The rendezvous is a city which appears in both agents’ shortest routes to the headquarters and is farthest from the headquarters. This year, the director of TSA has planned K missions that will be assigned to K pairs of secret agents. He is quite interested in finding the most popular rendezvous of the year, which is the rendezvous for the largest number of missions. Given a road system
among N cities and a list of cities assigned to agents in K missions, your task is to write a program to determine the most popular rendezvous.
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 25. The following lines describe the data sets.
For each data set, the first line contains two integers N (N ≤ 100 000) and K (K ≤ 100 000). The ith line
of the following N-1 lines contains two integers u and v (1 ≤ u,v ≤ N) separated by a space indicating that there is a two-way road between city u and v. The jth line the next K lines contains two integers x and y (1 ≤ x,y ≤ N) separated by space describing the two cities assigned to two secret agents in the jth mission.
For each data set, write in one line the identifier of the city which is the most popular rendezvous. In case there are more than one solution, write the smallest identifier.
1 9 3 1 8 1 4 1 9 9 7 4 6 6 3 4 2 4 5 5 3 2 6 7 8
4
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
| No. | Testdata Range | Score |
|---|