시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 24 11 9 40.909%

문제

여러분도 모두 알다시피, 경기과학고는 수원시 장안구 송죽동에 세워져 있다. 하지만, 사실 여러분이 아는 송죽동이 전부가 아니었으니... 여러분이 잠든 사이, 송죽동은 음침하고 위험한 도시 '현수시티'의 일부가 된다.

현수시티는 어둠에 잠긴 무서운 곳이지만, 사실 현수시티의 시장 현수는 무서운 사람이 아니다. 그는 단지 어두운 게 좋아 현수시티를 세웠을 뿐인데, 어둡다는 이유로 사람들이 모두 기피하고 범죄의 온상이 되어 버린 것이다.

현수시티는 $1$에서 $N$까지 번호가 붙은 $N$개의 교차로가 $M$개의 도로들로 연결되어 있는 형태인데, 임의의 교차로 사이를 도로들을 통해 오갈 수 있도록 되어 있다. 착한 현수는 모든 도로에 가로등을 하나씩 설치하고, 사람들이 길을 잃지 않도록 모든 도로가 최대 한 개의 사이클에 속하도록 도시를 설계했다.

현수에게는 요즘 새로운 고민이 생겼는데, 도로에 있는 가로등이 자꾸 고장난다는 것이다. 고장나는 대로 고치고는 있지만 역부족이었다. 가로등이 꺼진 도로를 지나다니는 것은 정말 위험하므로, 현수는 시민들이 가로등이 켜진 길로만 다닐 수 있었으면 한다. 이를 위해, 현수는 사람들이 어떤 두 교차로 사이를 가로등이 켜진 길로만 오갈 수 있는지 실시간으로 알려주는 앱을 만들려고 한다.

현수는 바쁘기 때문에 앱을 만드는 일을 당신에게 맡겼다. 현수를 도와주자!

입력

첫 번째 줄에는 교차로의 개수 $N$ ($1 \le N \le 200\, 000$) 과 도로의 개수 $M$ ($N-1 \le M \le 200\, 000$) 이 주어진다.

다음 $M$개의 줄에는 각 도로가 잇는 두 교차로의 번호 $u_i$, $v_i$가 주어진다. ($1 \le u_i, v_i \le N$)

중복 간선이나 셀프 루프는 들어오지 않으며, 모든 간선이 최대 한 개의 사이클에 속함이 보장된다.

그 다음 줄에는 입력에서 $i$번째로 들어온 도로의 가로등이 작동하는지의 여부가 공백을 사이에 두고 순서대로 주어진다. 작동하면 $1$, 고장났으면 $0$이다.

그 다음 줄에는 앱에 들어오는 갱신 / 질의의 수 $Q$ ($1 \le Q \le 200\, 000$) 가 주어진다.

다음 $Q$개의 줄에는 각 갱신 / 질의의 정보가 순서대로 주어진다. 각 줄에는 $2$개 또는 $3$개의 숫자가 주어지고, 의미는 다음과 같다 :

$1$ $i$ : 입력에서 $i$번째로 들어온 도로에 있는 가로등의 상태가 바뀐다. (고장났다면 고쳐지고, 작동 중이었다면 고장난다)

$2$ $a$ $b$ : 현재 도로 상태에서 $a$번 교차로에서 $b$번 교차로 사이를 가로등이 켜진 길만 이용해서 오갈 수 있는지 물어보는 질의이다.

출력

각 질의($t=2$인 입력)에 대해, 해당하는 두 교차로를 가로등이 켜진 길만 이용해 오갈 수 있다면 "YES", 아니면 "NO"를 출력한다. (따옴표 제외)

예제 입력 1

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

예제 출력 1

YES
NO
YES