18932번 - 트리와 쿼리 16

문제

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$ 형태의 쿼리의 답을 한 줄씩 출력한다.

제한

힌트