题目描述

Gildong 正在山中徒步，路过了数以百万计的树。受它们启发，他突然想到了数据结构中关于树的一个有趣想法：如果我们在一棵树中再加一条边会怎样？

然后他发现，这种类似树的图被称为 1-树。由于 Gildong 已经厌倦了解太多树上问题，他想看看树上的类似技巧是否也能用于 1-树。与其自己解决，他打算通过提供关于 1-树的询问来考验你。

首先，他会给你一棵有 $n$ 个顶点的树（不是 1-树），然后他会询问你 $q$ 个问题。每个询问包含 $5$ 个整数：$x$、$y$、$a$、$b$ 和 $k$。这表示你需要判断，在顶点 $x$ 和 $y$ 之间添加一条双向边之后，是否存在一条从顶点 $a$ 到 $b$ 的路径，恰好包含 $k$ 条边。一条路径可以多次经过相同的顶点和相同的边。所有询问彼此独立；也就是说，一个询问中添加的边会在下一个询问中被移除。

输入格式

第一行包含一个整数 $n$（$3 \le n \le 10^5$），表示树的顶点数。

接下来 $n-1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n$，$u \ne v$），表示顶点 $u$ 和 $v$ 之间有一条边。所有边都是双向且互不相同的。

下一行包含一个整数 $q$（$1 \le q \le 10^5$），表示 Gildong 想要询问的次数。

接下来 $q$ 行每行包含五个整数 $x$、$y$、$a$、$b$ 和 $k$（$1 \le x,y,a,b \le n$，$x \ne y$，$1 \le k \le 10^9$）——这些整数的含义已在题目描述中说明。保证顶点 $x$ 和 $y$ 之间的边不存在于原树中。

输出格式

对于每个询问，如果在顶点 $x$ 和 $y$ 之间添加一条边后，存在一条从顶点 $a$ 到 $b$ 且恰好包含 $k$ 条边的路径，则输出 "YES"。否则，输出 "NO"。

你可以以任意大小写形式输出每个字母（大写或小写均可）。

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

YES
YES
NO
YES
NO

提示

下图描述了这棵树（圆点和实线）以及每个询问中添加的边（虚线）。

对于答案为 "YES" 的询问，可能的路径如下：

• 第 $1$ 个询问：$1$ – $3$ – $2$
• 第 $2$ 个询问：$1$ – $2$ – $3$
• 第 $4$ 个询问：$3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$