F. Friends Reunion at the Park
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the heart of the enchanting town of Graphville lies Vertex Park, an expanse of lush landscapes intertwined with a complex network of pathways. This park, renowned for its verdant groves and serene ambiance, serves as a cherished rendezvous for three inseparable friends: Alice, Bob, and Carol. Unlike the typical parks, Vertex Park boasts a unique design resembling a tree structure, with pathways ensuring direct and loop-free connections between its various junctions.

One sunny afternoon, inspired by the interconnectedness of the park, the trio conceives a playful challenge: starting from different locations within the park, they aim to ascertain the minimal steps necessary for a joint gathering at a single junction. This venture seeks not just to test their understanding of the park's layout but to maximize their time together amidst nature's bounty. Given the uniform length of the pathways and the strategic starting points of Alice, Bob, and Carol, your task is to calculate the fewest steps required for their reunion, thereby facilitating an extended companionship in their verdant haven.

Input

The narrative unfolds with an integer $$$N$$$ ($$$3 \leq N \leq 2*10^5$$$), symbolizing the number of junctions adorning Vertex Park. Subsequently, $$$N-1$$$ lines follow, each bearing two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$, $$$u \neq v$$$), delineating a pathway linking junctions $$$u$$$ and $$$v$$$. A new chapter begins with an integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), indicating the number of queries or challenges proposed by the friends. Each query is articulated through a line comprising three distinct integers $$$A$$$, $$$B$$$, and $$$C$$$ ($$$1 \leq A, B, C \leq N$$$), representing the initial positions of Alice, Bob, and Carol within the park's expanse.

Output

For every query, a single integer is to be revealed, symbolizing the minimal number of steps the trio must embark upon to achieve their reunion at a singular junction. This figure not only embodies the solution to their playful challenge but also epitomizes the essence of their friendship, intertwined within the labyrinthine paths of Vertex Park.

Example
Input
6
1 3
2 5
3 4
3 5
5 6
2
1 4 6
3 2 6
Output
2
1