← 返回题目列表

Codeforces · 500/G

G. 新年跑步

中文机器翻译题面 查看原题

树岛新年即将来临!在这个岛上,顾名思义,有 n 个城市由 n - 1 条道路连接,并且对于任何两个不同的城市,它们之间总是存在一条路径。对于树岛的每个人来说,经过一条路只需要一分钟。

树岛的跑步者有一个奇怪的新年传统,那就是“极限跑”。这个传统可以按如下方式完成。

跑步者选择两个不同的城市 a 和 b。为了简单起见,我们将从城市 a 到城市 b 的最短路径表示为 p1, p2, ..., pl (这里,p1 = a 且 pl = b 成立)。然后发生以下情况:

1. 跑步者从a城市出发。
2. 跑步者从a城市跑到b城市,沿着从a城市到b城市的最短路径。
3. 当跑步者到达b城市时,他立即转向(不需要时间),沿着从b城市到a城市的最短路径向a城市跑去。
4. 当跑步者到达a城市时,他立即转向(不需要时间),沿着从a城市到b城市的最短路径向b城市跑去。
5. 永远重复步骤 3 和步骤 4。

简而言之,跑步者的路线可以表示为: $$p_1\to p_2\to\cdots\to p_{l-1}\to p_{l-2}\to p_1$$ $$\overrightarrow{p_2} \to \cdots \to \overrightarrow{p_{l-1}} \to \overrightarrow{p_1} \to \cdots \to \overrightarrow{p_2}$$

两位跑步者JH和JY决定“极限”跑步以庆祝新年。 JH 选择了两个城市 u 和 v,JY 选择了两个城市 x 和 y。他们决定在同一时刻开始跑步,一直跑到在同一个城市第一次相遇。路上相遇对他们来说并不重要。在跑步之前,他们想知道自己要跑多少时间。

JH和JY很难计算这个,所以他们向你寻求帮助。

输入

第一行包含一个正整数 n (5 ≤ n ≤ 2 × 105) — 树岛的城市数量。

接下来的 n - 1 行描述了树岛的道路。其中第 i 行 (1 ≤ i ≤ n - 1) 包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 由树的单条路连接的顶点。

下一行包含一个整数 t (1 ≤ t ≤ 2 × 105) — 测试用例的数量。

接下来的 t 行描述了测试用例。其中第 j 行 (1 ≤ j ≤ t) 包含四个空格分隔的整数 uj, vj, xj, yj (1 ≤ uj, vj, xj, yj ≤ n, uj ≠ vj, xj ≠ yj)。这意味着在这个测试用例中,JH选择了两个城市uj和vj,JY选择了两个城市xj和yj。 JH 开始在城市 uj 运行,JY 开始在城市 xj 运行。

输出

对于每个测试用例,打印一个整数,描述它们应该运行的时间(以分钟为单位)。如果他们必须运行无限长的时间(换句话说,如果他们从未在同一个城市相遇),则打印 -1 。如果它们在运行开始时相遇,则打印 0。

示例

输入 #1

7
1 3
3 6
7 4
3 7
5 4
7 2
4
6 5 5 3
3 5 4 6
1 5 1 3
1 5 3 1

输出 #1

2
1
0
-1

注意

该示例如下所示: