Isfandiyor founded the country of Lipland. Lipland has \(n\) cities with \(n-1\) roads between them (in other words, Lipland is a tree – a simple, connected, acyclic graph).
Isfandiyor named city \(1\) the capital of Lipland. Then he went to the city nearest to city \(1\) that was not yet numbered (if several were equally near, he picked any) and named it city \(2\). Then he went to the unnumbered city nearest to city \(2\) and named it city \(3\). Continuing in this manner, he numbered all cities with \(1 \dots n\).
Let \(dist(a, b)\) denote the length of the shortest path from city \(a\) to city \(b\). You are given \(q\) queries, each with a number \(x\). Your task is to find the lexicographically smallest pair \((a, b)\) satisfying \(dist(a, b) \ge x\).
The first line contains a natural number \(n\) (\(2 \le n \le 200\,000\)).
Each of the next \(n-1\) lines contains numbers \(a\) and \(b\) of two adjacent cities (\(1 \le a, b \le n\), \(a \neq b\)).
The next line contains a natural number \(q\) (\(1 \le q \le 200\,000\)).
Each of the next \(q\) lines contains an integer \(x\) (\(0 \le x < n\)).
It is guaranteed that the given graph is a tree and that the cities are numbered exactly the way Isfandiyor wanted.
For each query, print the lexicographically smallest pair if one exists, otherwise print two numbers \(-1\).
8 1 2 2 3 2 4 4 5 5 6 4 7 1 8 4 0 2 5 6
1 1 1 3 6 8 -1 -1