시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 512 MB | 144 | 18 | 8 | 8.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 = 2$ 형태의 쿼리의 답을 한 줄씩 출력한다.
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 2 1