1-트리와 쿼리

길동이는 산을 오르며 수많은 나무 사이를 걸었다. 나무에서 영감을 받아 자료구조의 트리에 관해 흥미로운 아이디어를 떠올렸다. 트리에 간선을 하나 더 추가하면 어떻게 될까?

그는 이런 트리 모양의 그래프가 1-트리라고 불린다는 것을 알게 되었다. 길동이는 트리 문제를 너무 많이 풀어서 지겨웠기에, 트리에서 쓰는 기법이 1-트리에서도 통하는지 알고 싶었다. 직접 풀지 않고, 1-트리 위의 쿼리를 주어 당신을 시험하기로 했다.

먼저 정점이 $n$개인 트리(1-트리가 아님)가 주어진다. 그다음 $q$개의 쿼리가 주어진다. 각 쿼리는 정수 $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$)가 한 줄에 하나씩 주어지며, 두 정점 사이에 간선이 있음을 뜻한다. 모든 간선은 양방향이고 서로 다르다.

다음 줄에 쿼리의 개수 $q$ ($1 \le q \le 10^5$)가 주어진다.

이후 $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"를 출력한다.

대문자와 소문자는 어느 쪽으로 출력해도 된다.

아래 그림은 트리(원과 실선)와 각 쿼리에서 추가되는 간선(점선)을 나타낸다.

"YES"로 답하는 쿼리의 경로 예시는 다음과 같다.

• 1번째 쿼리: 1-3-2
• 2번째 쿼리: 1-2-3
• 4번째 쿼리: 3-4-2-3-4-2-3-4-2-3