Tree Queries

n개의 정점(1부터 n까지 번호가 매겨져 있다)으로 이루어진 트리가 주어진다. 처음에는 모든 정점이 흰색이다. 서로 다른 두 유형의 쿼리 q개를 처리해야 한다:

1. 1 x — 정점 x의 색을 검은색으로 바꾼다. 첫 번째 쿼리는 이 유형임이 보장된다.
2. 2 x — 정점 x에 대해, 인덱스가 y인 정점이 x에서 어떤 검은색 정점까지의 단순 경로에 속하도록 하는 최소 인덱스 y를 구한다(단순 경로는 어떤 정점도 두 번 이상 방문하지 않는다).

유형 2의 각 쿼리에 대한 답을 출력한다.

쿼리가 변형된 형태로 주어진다는 점에 유의한다.

첫 번째 줄에 두 수 n와 q가 주어진다 (3 ≤ n, q ≤ 106).

이어서 n - 1개의 줄이 주어지며, 각 줄에는 두 수 xi와 yi가 주어지고 (1 ≤ xi < yi ≤ n), 정점 xi와 yi 사이의 간선을 나타낸다.

이 간선들이 트리를 이룸이 보장된다.

이어서 q개의 줄이 주어진다. 각 줄에는 두 정수 ti와 zi가 주어지며, ti는 i번째 쿼리의 유형이고, zi는 다음과 같은 방식으로 이 쿼리의 xi를 복원하는 데 사용할 수 있다. 유형 2인 last 쿼리의 답 (let's call this answer last, and initially last = 0)를 계속 추적해야 한다. 그러면 xi = (zi + last) mod n + 1이다.

첫 번째 쿼리는 유형 1이며, 유형 2인 쿼리가 적어도 하나 존재함이 보장된다.

유형 2의 각 쿼리에 대한 답을 출력한다.