Elevated Rails

Brandon and Geoffry like trains! They have been tasked with building a network of rails connecting $n$ train stations. Each station is on one of three islands, and each island has at least one station on it.

Brandon has set up enough connections between stations on the same island so that there is exactly one way to take a train between any two stations on that island without visiting the same station twice. However, it is not yet possible to take a train between stations on different islands.

Geoffry asks several questions about Brandon's network. Each question picks two stations on different islands and asks for the maximum number of stations that a path between them could take if Brandon adds exactly two more connections so that every station can reach every other station. Brandon is too busy with rail signals to think about connecting the islands, so he leaves all of Geoffry's questions to you.

The first line contains two integers $n$ and $q$ ($3 \le n \le 10^5$, $1 \le q \le 2 \cdot 10^5$), the number of stations and the number of questions.

Each of the next $n - 3$ lines contains two integers $x$ and $y$ ($1 \le x < y \le n$), meaning stations $x$ and $y$ are connected by a rail that can be used in both directions.

The current rail connections satisfy the conditions above. The $n$ stations can be grouped into three islands so that two stations can reach each other if and only if they are on the same island, and there is a unique path between any two stations on the same island that does not repeat any station.

Each of the next $q$ lines contains two integers $a$ and $b$, asking for the maximum number of stations that could appear on a path between station $a$ and station $b$. It is guaranteed that stations $a$ and $b$ are on different islands.

Each question is independent of the others.

Output $q$ lines, one per question. The answer to each question is a single integer: the maximum number of stations that could appear on a path between station $a$ and station $b$.