시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB63453676.596%

문제

한국항공대학교는 $n$ 개의 건물로 이루어져 있으며, 두 건물을 잇는 여러 개의 도로가 존재한다. 결벽증이 있는 동원이는, 한번도 가지 않은 길을 무서워한다. 동원이는 항공대의 여러 도로들 중 $n-1$ 개의 도로를 선택해서 그 도로로만 다니기로 하였다. 

어떠한 건물 $x$에서 어떠한 건물 $y$ 로 이동한다는 것은, $x$ 에 연결된 도로를 타고 다른 건물로 이동하는 것을 반복하여 $y$ 에 도달할 수 있다는 것이다. 예를 들어, $3$ 개의 건물이 있고, $(1, 2), (2, 3)$ 번 건물 사이에 도로가 있다면, $1$번 건물에서 $3$번 건물로 이동한다는 것은

  • $1$번 건물을 거치고, 
  • 건물 $(1, 2)$ 를 잇는 도로를 지나고,
  • $2$번 건물을 거치고, 
  • 건물 $(2, 3)$ 을 잇는 도로를 지나고,
  • $3$번 건물을 거쳐서 도착

한다는 것이다. 이 과정에서 $3$개의 건물과 $2$개의 도로를 거쳤다. 동원이는 도로를 섬세하게 골랐기 때문에, 동원이가 고른 $n-1$ 개의 도로들만을 사용해서, 임의의 건물 $i$ ($1 \le i \le n$) 에서 $j$ ($1 \le j \le n$) 으로 항상 이동할 수 있다.

한국항공대학교는 학생들의 편의를 위해서 도로들과 건물들을 공사하고 있다. 만약 어떠한 건물이나 도로가 공사중이라면, 이동을 할 때 이 건물이나 도로를 거쳐갈 수 없다. 이 조건에 따라 다음과 같은 $q$ 개의 질문을 해결하라.

  • 1 i j k: $k$ 번 건물이 공사 중일때, $i$ 번 건물에서 $j$ 번 건물로 이동할 수 있는가? ($1 \le i, j, k \le n$)
  • 2 i j k l: $k$ 번 건물과 $l$ 번 건물을 잇는 도로가 공사 중일때, $i$ 번 건물에서 $j$ 번 건물로 이동할 수 있는가? 동원이가 고른 도로 중 $k$ 번 건물과 $l$ 번 건물을 잇는 도로가 존재함이 보장된다. ($1 \le i, j, k, l \le n$)

입력

첫 번째 줄에 정수 $n$ 이 주어진다. ($2 \le n \le 250\,000$)

이후 $n-1$ 개의 줄에 동원이가 고른 도로가 잇는 두 건물의 번호 $x, y$ 가 주어진다. ($1 \le x, y \le n, x \neq y$)

다음 줄에 정수 $q$ 가 주어진다. ($1 \le q \le 250\,000$)

이후 $q$ 개의 줄에 질문이 위에서 설명한 형식대로 주어진다.

출력

$q$ 개의 줄에 걸쳐 질문의 정답을 YESNO로 출력하라.

예제 입력 1

4
1 2
2 3
2 4
13
1 1 3 1
1 1 3 2
1 1 3 3
1 1 3 4
1 1 1 2
1 1 1 1
2 1 2 2 4
2 1 2 1 2
2 1 3 1 2
2 1 3 2 3
2 1 3 2 4
2 1 1 1 2
2 1 1 2 4

예제 출력 1

NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
YES
YES
YES