도로 정비

IOI국은 $N$개의 도시로 이루어진 나라이다. 도시에는 $1, 2, \ldots, N$의 번호가 붙어 있다. JOI 교수는 IOI국의 도로망이 정비된 과정에 관심을 가졌다.

JOI 교수가 IOI국의 역사에 관한 자료를 조사한 결과, 다음 사실을 알았다.

• IOI국의 도시는 건국 직후부터 현재까지 같다. IOI국의 건국 직후에는 도시를 잇는 도로가 하나도 없었다.
• IOI국의 건국 $i$년 후 ($1 \le i \le Q$)에 도시 $A_i$와 도시 $B_i$ 사이의 교통 상황 개선 계획이 세워졌다.
• 세워진 개선 계획 중 일부는 계획대로 실행되었고, 실행되지 않고 폐기된 계획도 있다.
• 어떤 개선 계획이 실행되었는지는 자료에서 분명히 드러난다.
• 실행된 개선 계획은 모두 1년 이내에 실행이 완료되었다.

또 다른 문헌에서, 도시 $A_i$와 도시 $B_i$ 사이의 교통 상황 개선 계획이 다음과 같다는 것을 알았다.

• 개선 계획이 세워진 시점에 건설된 도로로 도시 $A_i$에서 도시 $B_i$로 이동할 수 없으면, 도시 $A_i$와 도시 $B_i$를 양방향으로 잇는 도로를 새로 건설한다. 새로 건설된 도로는 비포장이다.
• 개선 계획이 세워진 시점에 건설된 도로로 도시 $A_i$에서 도시 $B_i$로 이동할 수 있으면, 그러한 경로 중 사용하는 도로의 수가 최소인 경로에 포함된 비포장 도로를 모두 포장한다. 사용하는 도로의 수가 최소인 경로가 여러 개면, 그 경로 모두에 대해 같은 방식으로 비포장 도로를 포장한다. 한 번 포장한 도로를 다시 포장하지는 않는다.

JOI 교수는 추가 조사를 위해, 실행되지 않고 폐기된 개선 계획 각각에 대해, 만약 그 개선 계획만 추가로 실행되었다면 그 개선 계획에서 도로를 몇 개 포장하게 되었는지 계산하기로 했다.

IOI국의 교통 상황 개선 계획과 그 실행 상황이 주어졌을 때, 실행되지 않고 폐기된 개선 계획 각각에 대해, 만약 그 개선 계획이 실행되었다면 그 개선 계획에서 포장하게 되었을 도로의 수를 계산하는 프로그램을 작성하시오.

표준 입력에서 다음 데이터를 읽는다.

• 1번째 줄에는 정수 $N$, $Q$가 공백을 구분으로 쓰여 있다. 이는 IOI국에 도시가 $N$개 있고, JOI 교수가 건국부터 $Q$년 동안의 교통 상황 개선 계획에 주목하고 있음을 나타낸다.
• 이어지는 $Q$개의 줄 중 $i$번째 줄 ($1 \le i \le Q$)에는 3개의 정수 $T_i$, $A_i$, $B_i$가 공백을 구분으로 쓰여 있다. 정수 $T_i$는 건국 $i$년 후에 세워진 개선 계획의 실행 상황을 나타내며, $T_i = 1$일 때는 그 개선 계획이 실행되었음을, $T_i = 2$일 때는 그 개선 계획이 실행되지 않고 폐기되었음을 나타낸다. 정수 $A_i$, $B_i$는 건국 $i$년 후에 도시 $A_i$와 도시 $B_i$ 사이의 교통 상황 개선 계획이 세워졌음을 나타낸다.

표준 출력에, 실행되지 않고 폐기된 개선 계획 각각에 대해, 만약 그 개선 계획이 실행되었다면 그 개선 계획에서 포장하게 될 도로의 수를 1줄에 출력하시오. 단, 그 개선 계획을 실행하면 새로운 도로가 건설되는 경우에는 -1을 출력하시오.

• $2 \le N \le 100\,000$.
• $1 \le Q \le 300\,000$.
• $1 \le T_i \le 2$ ($1 \le i \le Q$).
• $1 \le A_i \le N$ ($1 \le i \le Q$).
• $1 \le B_i \le N$ ($1 \le i \le Q$).
• $A_i \ne B_i$ ($1 \le i \le Q$).