Gildong was hiking a mountain, walking by millions of trees. Inspired by them, he suddenly came up with an interesting idea for trees in data structures: What if we add another edge in a tree?

Then he found that such tree-like graphs are called 1-trees. Since Gildong was bored of solving too many tree problems, he wanted to see if similar techniques in trees can be used in 1-trees as well. Instead of solving it by himself, he's going to test you by providing queries on 1-trees.

First, he'll provide you a tree (not 1-tree) with $n$ vertices, then he will ask you $q$ queries. Each query contains $5$ integers: $x$, $y$, $a$, $b$, and $k$. This means you're asked to determine if there exists a path from vertex $a$ to $b$ that contains exactly $k$ edges after adding a bidirectional edge between vertices $x$ and $y$. A path can contain the same vertices and same edges multiple times. All queries are independent of each other; i.e. the added edge in a query is removed in the next query.


-----Input-----

The first line contains an integer $n$ ($3 \le n \le 10^5$), the number of vertices of the tree.

Next $n-1$ lines contain two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$) each, which means there is an edge between vertex $u$ and $v$. All edges are bidirectional and distinct.

Next line contains an integer $q$ ($1 \le q \le 10^5$), the number of queries Gildong wants to ask.

Next $q$ lines contain five integers $x$, $y$, $a$, $b$, and $k$ each ($1 \le x,y,a,b \le n$, $x \ne y$, $1 \le k \le 10^9$) – the integers explained in the description. It is guaranteed that the edge between $x$ and $y$ does not exist in the original tree.


-----Output-----

For each query, print "YES" if there exists a path that contains exactly $k$ edges from vertex $a$ to $b$ after adding an edge between vertices $x$ and $y$. Otherwise, print "NO".

You can print each letter in any case (upper or lower).


-----Example-----
Input
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

Output
YES
YES
NO
YES
NO



-----Note-----

The image below describes the tree (circles and solid lines) and the added edges for each query (dotted lines). [Image] 

Possible paths for the queries with "YES" answers are:   $1$-st query: $1$ – $3$ – $2$  $2$-nd query: $1$ – $2$ – $3$  $4$-th query: $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$

Difficulty: interview

Starter code:

Solutions:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from collections import deque

class LCA():
    def __init__(self, G, root):
        self.n = len(G)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]

        def bfs(root):
            que = deque()
            que.append((-1,root,0))
            while que:
                p,v,d = que.pop()
                self.dep[v]=d
                self.par[0][v]=p
                for to in G[v]:
                    if to != p:
                        que.append((v,to,d+1))

        bfs(root)

        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        lca = self.lca(a,b)
        return self.dep[a]+self.dep[b]-2*self.dep[lca]

n = int(input())
G = [[] for i in range(n)]

for i in range(n-1):
    a,b = list(map(int, input().split()))
    a,b = a-1,b-1
    G[a].append(b)
    G[b].append(a)

L = LCA(G, 0)

q = int(input())
for i in range(q):
    x,y,a,b,k = list(map(int, input().split()))
    x,y,a,b = x-1,y-1,a-1,b-1

    ab = L.dist(a,b)
    base = [ab]

    ax = L.dist(a,x)
    ay = L.dist(a,y)
    bx = L.dist(b,x)
    by = L.dist(b,y)

    base.append(ax+1+by)
    base.append(ay+1+bx)

    flag = any(ki<=k and (k-ki)%2==0 for ki in base)

    if flag:
        print("YES")
    else:
        print("NO")



from collections import deque
import sys
input = sys.stdin.readline


class LowestCommonAncestor():
    def __init__(self, tree, root):
        self.n = len(tree)
        self.depth = [0] * self.n
        self.log_size = (self.n).bit_length()
        self.parent = [[-1] * self.n for i in range(self.log_size)]

        q = deque([(root, -1, 0)]) 
        while q:
            v, par, dist = q.pop()
            self.parent[0][v] = par
            self.depth[v] = dist
            for child_v in tree[v]:
                if child_v != par:
                    self.depth[child_v] = dist + 1
                    q.append((child_v, v, dist + 1))

        for k in range(1, self.log_size):
            for v in range(self.n):
                self.parent[k][v] = self.parent[k-1][self.parent[k-1][v]]
            
    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u
        for k in range(self.log_size):
            if (self.depth[v] - self.depth[u] >> k) & 1:
                v = self.parent[k][v]
        if u == v:
            return u
          
        for k in reversed(range(self.log_size)):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]


n = int(input())
info = [list(map(int, input().split())) for  i in range(n - 1)]

tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    
lca = LowestCommonAncestor(tree, 0)

q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
    
for i in range(q):
    x, y, a, b, k = query[i]
    lca_ab = lca.lca(a - 1, b - 1)
    ab = lca.depth[a - 1] + lca.depth[b - 1] - 2 * lca.depth[lca_ab]
    lca_xy = lca.lca(x - 1, y - 1)
    xy = lca.depth[x - 1] + lca.depth[y - 1] - 2 * lca.depth[lca_xy]

    lca_ax = lca.lca(a - 1, x - 1)
    lca_ay = lca.lca(a - 1, y - 1)
    lca_bx = lca.lca(b - 1, x - 1)
    lca_by = lca.lca(b - 1, y - 1)
    
    ax = lca.depth[a - 1] + lca.depth[x - 1] - 2 * lca.depth[lca_ax]
    ay = lca.depth[a - 1] + lca.depth[y - 1] - 2 * lca.depth[lca_ay]
    bx = lca.depth[b - 1] + lca.depth[x - 1] - 2 * lca.depth[lca_bx]
    by = lca.depth[b - 1] + lca.depth[y - 1] - 2 * lca.depth[lca_by]
    if ab <= k and k % 2 == ab % 2:
        print("YES")
    elif ax+1+by <= k and k % 2 == (ax+1+by) % 2:
        print("YES")
    elif ay+1+bx <= k and k % 2 == (ay+1+bx) % 2:
        print("YES")
    else:
        print("NO")