도로 정비와 수도까지의 거리

어느 나라가 도로 정비 계획을 발표했다. 계획에는 두 도시를 잇는 도로를 새로 놓는 작업과 이미 놓인 도로를 없애는 작업이 들어 있다. 정비는 계획에 적힌 순서대로 한 번에 하나씩 진행한다. 앞선 작업으로 놓은 도로를 뒤의 작업에서 다시 없앨 수도 있다.

이 나라의 수도는 1번 도시다. 각 도시에서 수도까지 가려면 도로를 최소 몇 개 지나야 하는지, 정비 작업을 하나 마칠 때마다 조사하려고 한다. 도로는 양방향이고, 수도 자신은 도로를 하나도 지나지 않으므로 항상 0이다.

처음 도로 상태와 정비 계획이 주어질 때, 작업을 하나 끝낼 때마다 도시별 답을 출력하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $n$과 처음에 놓여 있는 도로의 수 $m$이 주어진다. ($2 \le n \le 500$, $1 \le m \le n(n-1)/2$)

다음 $m$개 줄에는 도로 하나가 잇는 두 도시의 번호가 주어진다.

그다음 줄에 정비 계획에 들어 있는 작업의 수 $q$가 주어진다. ($1 \le q \le 500$)

이어지는 $q$개 줄에는 정수 세 개 $a$, $i$, $j$가 주어진다. $a$가 1이면 도시 $i$와 도시 $j$를 잇는 도로를 새로 놓고, $a$가 2이면 두 도시를 잇는 도로를 없앤다. ($1 \le a \le 2$, $1 \le i, j \le n$, $i \ne j$)

같은 두 도시를 잇는 도로는 많아야 하나다. 이미 있는 도로를 또 놓거나 없는 도로를 없애는 입력은 주어지지 않는다.

$q$개 줄을 출력한다. $k$번째 줄에는 $k$번째 작업을 마친 뒤의 답을 1번 도시부터 $n$번 도시까지 순서대로, 공백 하나로 구분해 출력한다.

어떤 도시의 답은 그 도시에서 수도까지 가는 데 지나야 하는 도로의 최소 개수다. 수도에 갈 수 없는 도시는 -1을 출력한다.