Graph Search 2

King zych of Namgyu announced a road construction plan. The plan lists roads between pairs of cities in order, and because building one road is a large job, the crew builds them one at a time in the listed order.

To prepare the next plan, zych measures the shortest route from every city to the capital after each road is built. The value of city $i$ is the minimum number of roads you pass when you travel from city $i$ to the capital. The value of the capital itself is $0$, and if no sequence of roads reaches the capital, the value is $-1$.

You are given the initial cities and roads together with the construction plan. Write a program that prints the value of city $1$ through city $n$ after each road is built.

The first line contains the number of cities $n$ and the number of roads that already exist $m$. ($2 \le n \le 1000$, $1 \le m \le 100000$)

Each of the next $m$ lines contains the numbers of the two cities that a road connects.

The next line contains the number of roads in the construction plan $q$. ($1 \le q \le 500$)

Each of the following $q$ lines contains two integers $i$ and $j$, meaning that a new road between city $i$ and city $j$ is built. ($1 \le i, j \le n$)

Every road is bidirectional. Several roads may connect the same pair of cities, and $i$ may equal $j$. The capital is city $1$.

Print $q$ lines. On line $t$, print the value of city $1$ through city $n$ after the first $t$ roads of the plan are built, separated by single spaces.