Circumcenter of a Tree

Donggwan, absorbed in algorithms and now fixated on trees, wants to define a circumcenter in a tree. A tree is a connected graph with no cycles. But Donggwan realized that defining a circumcenter in a tree requires first defining "the distance between two vertices in a tree."

In a tree, the distance between two vertices is defined as the minimum number of edges that must be traversed to get from one vertex to the other. For three vertices of a tree, the circumcenter of the tree is defined as a vertex whose distances to the three vertices are all equal and as small as possible, if such a vertex exists. Mathematically, one can show that for three vertices of a tree, the circumcenter is unique if it exists.

It is obvious that changing the three vertices that define the circumcenter changes the circumcenter even for the same tree. Donggwan wants to find many different circumcenters but finds coding a nuisance. Write the code for Donggwan.

The first line gives the number of vertices $N$. ($1 \le N \le 100{,}000$) The tree consists of vertex 1, vertex 2, ..., vertex $N$.

From the second line to the $N$-th line, two positive integers $X$ and $Y$ representing the edge information of the tree are given, separated by a space. This means that vertex $X$ and vertex $Y$ are connected. ($1 \le X, Y \le N$, $X \neq Y$)

The given connections form a tree.

The $N+1$-th line gives the number of queries $Q$. ($1 \le Q \le 100{,}000$)

Over the next $Q$ lines, three positive integers $A$, $B$, $C$ representing the three vertices that define the circumcenter are given, separated by spaces. ($1 \le A, B, C \le N$)

For each query over $Q$ lines, output the vertex number of the circumcenter if the circumcenter of the tree for the three given vertices exists, or -1 if it does not.