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