시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 14 3 2 40.000%

문제

N개의 정점으로 이루어진 그래프가 있을 때 다음 쿼리를 해결하는 프로그램을 작성하시오.

  1. x y : x와 y 사이에 간선이 존재하면 제거하고, 존재하지 않으면 추가하는 쿼리이다. (0 ≤ x < y < N)
  2. x y : x와 y가 같은 연결 요소에 속하는지 여부를 구하여 출력하는 쿼리이다.  (0 ≤ y < x < N)

입력

첫째 줄에 정점의 갯수 N과 쿼리의 갯수 Q가 공백으로 구분하여 주어진다. ( 2 ≤ N, Q ≤ 105)

둘째 줄부터 Q개의 줄에 걸쳐 쿼리에 해당하는 두 정수 a b가 주어진다. (0 ≤ a, b < 263​​​​, a ≠ b)

x = (a xor F) mod N, y = (b xor F) mod N이며 F는 최초 0이고, 각 쿼리를 실행한 직후의 연결 요소의 갯수가 더해진다.

출력

2번 쿼리의 결과를 각 줄에 출력하시오. 두 정점이 같은 연결 요소에 속할 경우 1을, 아니면 0을 출력한다.

예제 입력 1

5 5
1 2
5 7
5 6
14 15
6 7

예제 출력 1

1
0
0

출처

  • 문제를 만든 사람: Lawali