说明

给定一个无根的加权树 $T$，其顶点为 $1, 2, \ldots, n$。请回答一些查询。

我们定义 $\texttt{dist}(i,j)$ 为顶点 $i$ 和顶点 $j$ 在树 $T$ 中的距离。

对于每个查询，给定两个整数 $l, r$。请回答以下值：

输入格式

第一行包含一个整数 $n~(1\leq n\le 2 \times 10^5)$，表示树中的顶点数。

接下来的 $n-1$ 行描述了树中的一条边。第 $i$ 条边由三个整数 $a_i, b_i, w_i$ $(1\le a_i, b_i\le n, 1\le w_i\le 10^9)$ 表示，分别为它连接的顶点的标签及其权重。

然后一行包含一个整数 $q~(1\leq q\le 10^6)$，表示查询的数量。

接下来的 $q$ 行中的每一行包含两个整数 $l, r~(1\le l \le r\le n)$，描述一个查询。

保证给定的边构成一棵树。

输出格式

对于每个查询，输出答案一行。如果不存在 $i,j$ 使得 $l\le i<j\le r$，则答案为 $-1$。

5
1 2 5
1 3 3
1 4 4
3 5 2
5
1 1
1 4
2 4
3 4
2 5

-1
3
7
7
2

提示

题面翻译由 ChatGPT-4o 提供。