시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 512 MB1351888.247%

문제

N개의 정점으로 이루어진 포레스트가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있다. 초기 포레스트에 간선은 없다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 u v: 두 정점 $u$, $v$ 를 잇는 간선을 포레스트에 추가하라. 이 쿼리가 호출되기 이전에, 포레스트 상에서 $u$와 $v$를 잇는 경로가 없음이 보장된다. 
  • 2 u k: $dist(u, v)$ 를 두 정점 $u, v$ 간의 최단 경로의 길이라고 정의하자. 만약 두 정점이 연결되어 있지 않다면 값은 $\infty$ 이다. $dist(u, v) = k$ 인 정점 $v$ 의 개수를 반환하라.

입력

첫 번째 줄에 두 정수 $N, Q$ 가 주어진다. ($1 \le N \le 100\,000, 1 \le Q \le 200\,000$)

이후 $Q$ 개의 줄에 세 정수로 쿼리의 정보 $t_i, a_i, b_i$ 가 주어진다. ($1 \le t_i \le 2, 0 \le a_i, b_i < n$)

$last$ 라는 추가 변수를 생각하자. 이 변수는 초기에 0이라는 값을 가진다.

  • $t_i = 1$ 일 경우, 쿼리의 인자 $u_i, v_i$는 다음과 같이 정의된다: $u_i = ((a_i + last) \mod n) + 1, v_i = ((b_i + last) \mod n) + 1$ 
  • $t_i = 2$ 일 경우, 쿼리의 인자 $u_i, k_i$ 는 다음과 같이 정의된다: $u_i = ((a_i + last) \mod n) + 1, k_i = ((b_i + last) \mod n)$ 이 쿼리에 대한 답을 계산한 후, $last$ 를 해당 쿼리의 답으로 갱신한다. 

출력

$t_i = 2$ 형태의 쿼리의 답을 한 줄씩 출력한다.

예제 입력 1

7 9
1 0 6
1 4 3
1 0 5
1 1 2
1 3 1
1 4 5
2 2 3
2 2 1
2 0 0

예제 출력 1

1
2
1

출처

  • 문제를 번역한 사람: koosaga