그래프 탐색 2

남규나라의 왕 zych가 도로 정비 계획을 발표했다. 계획에는 두 도시를 잇는 도로가 순서대로 적혀 있고, 도로를 놓는 공사는 규모가 커서 적힌 순서대로 한 번에 하나씩 진행한다.

zych는 다음 계획을 세울 때 참고하려고, 도로를 하나 놓을 때마다 각 도시에서 수도까지 가는 최단 경로를 조사한다. 도시 $i$의 값은 $i$에서 출발해 수도에 도착할 때까지 지나야 하는 도로의 최소 개수이다. 수도 자신의 값은 $0$이고, 도로를 어떻게 따라가도 수도에 도착하지 못하면 값은 $-1$이다.

처음의 도시와 도로 상태, 그리고 도로 정비 계획이 주어진다. 도로를 하나 놓을 때마다 $1$번 도시부터 $n$번 도시까지의 값을 출력하는 프로그램을 작성하시오.

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

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

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

이어지는 $q$개의 줄에는 두 정수 $i$와 $j$가 주어지며, 도시 $i$와 도시 $j$를 잇는 도로를 새로 놓는다는 뜻이다. ($1 \le i, j \le n$)

모든 도로는 양방향이다. 같은 두 도시를 잇는 도로가 여러 개일 수 있고, $i$와 $j$가 같을 수도 있다. 수도는 $1$번 도시이다.

$q$개의 줄을 출력한다. $t$번째 줄에는 계획의 $t$번째 도로까지 놓은 뒤 $1$번 도시부터 $n$번 도시까지의 값을 공백 하나로 구분해 출력한다.