동적 연결성과 쿼리 (Hard)

문제

Easy 버전과 Hard 버전의 차이는 쿼리의 암호화 여부 차이다.

$N$개의 정점으로 이루어진 그래프가 주어진다. 각 정점에는 $1$부터 $N$까지 번호가 매겨져 있고, 초기에는 각 정점 사이에 간선이 없다. 이때 다음 쿼리를 수행하는 프로그램을 작성해 보자.

• 1 u v: $u$번 정점과 $v$번 정점 사이에 간선이 없으면 간선을 추가하고, 있으면 제거한다.
• 2 u v: $u$번 정점과 $v$번 정점 사이에 경로가 존재하면 1을 출력하고, 없으면 0을 출력한다.

입력

첫째 줄에 $N$과 쿼리의 개수 $Q$가 주어진다. ($2\le N, Q\le 100\,000$)

둘째 줄부터 $Q$개의 줄에 걸쳐 쿼리 복원에 필요한 세 정수 $a$, $b$, $c$가 주어진다. ($0 \le a, b, c \le 2^{63}-1$)

쿼리는 다음과 같이 복원한다.

• 쿼리 종류 $=(a\oplus X) \mod 2 + 1$
• $u=(b\oplus X) \mod N + 1$
• $v=(c\oplus X)\mod N + 1$

단, $\oplus$는 Bitwise-XOR 연산이다. $X$는 초기에는 $0$이며, 매 쿼리 수행 이후 $u$번 정점이 속한 연결 요소의 크기가 더해진다. $u \neq v$임이 보장된다.

출력

2번 쿼리의 답을 한 줄에 하나씩 출력한다.

예제 입력 1

3 8
1 2 1
0 1 0
2 2 0
4 6 5
7 7 5
9 8 10
9 11 9
13 13 14

예제 출력 1

0
0
0
1

힌트

예제 입력 1의 복원된 쿼리는 순서대로 다음과 같다.

2 3 2
2 1 2
1 1 3
1 3 2
1 1 3
2 1 3
1 3 1
2 2 3