문제

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$개의 줄에 걸쳐 각 줄에 쿼리가 t u v의 형식으로 주어진다. ($1\le t \le 2; 1\le u, v\le N; u\neq v$)

출력

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

예제 입력 1

3 8
2 3 2
2 1 2
1 1 3
1 3 2
1 1 3
2 1 3
1 3 1
2 2 3

예제 출력 1

0
0
0
1