Jon and Winterfell

0

0 votes
Easy
Problem

Here are N houses in Winterfell and N-1 Roads(i.e. depicting a tree). Jon Snow lives in house number 1 so this can be considered as the root of the tree. Now there are G girls who live in various houses except house number 1. All of them want to propose Jon Snow. But Jon has some condition. He will accept the proposal of the girl who lives at a minimum distance from his house. Now the distance between the two houses is the number of roads between them.

If two or more girls are at the same minimum distance then he will accept the proposal of the girl who lives in a house with minimum house number. No two girls are in the same house.

Input :

The first line consists of N - number of houses.

Next N-1 lines follow the type a b which denotes there is a road between a and b. Next line consists of G. Next G lines consists of x where the girls live.

Output :

Print the number of the house of the girl who will be accepted.

Constraints :

  • 2 <= N <= 1000
  • 1 <= a, b <= N
  • 1 <= G <= N-1
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?