Under construction

Still being built. Things may change

Road work and the distance to the capital

Interview

Time limit2sMemory limit512 MB

Summary
After each of q edge insertions and deletions, output the shortest-path distance from every city to city 1, or -1 if unreachable.
Level

Medium4 of 10

Topics
BFS, Graph, Implementation, Brute force
Solved
No attempts yet

Problem

A country announced a road work plan. The plan contains jobs that build a new road between two cities and jobs that tear down a road that already exists. The jobs run one at a time, in the order given. A road built by an earlier job can be torn down by a later one.

The capital is city 1. After each job the country wants to know, for every city, the smallest number of roads you have to travel to reach the capital. Roads are two way, and the capital itself travels no road at all, so its answer is always 0.

Given the initial roads and the plan, print the answer for every city after each job.

Input

The first line contains the number of cities nn and the number of roads that exist at the start mm. (2≤n≤5002 \le n \le 500, 1≤m≤n(n−1)/21 \le m \le n(n-1)/2)

Each of the next mm lines contains the two cities joined by one road.

The next line contains the number of jobs in the plan qq. (1≤q≤5001 \le q \le 500)

Each of the next qq lines contains three integers aa, ii, jj. If aa is 1, a new road between city ii and city jj is built. If aa is 2, the road between those two cities is torn down. (1≤a≤21 \le a \le 2, 1≤i,j≤n1 \le i, j \le n, i≠ji \ne j)

At most one road joins any pair of cities. The input never builds a road that already exists and never tears down a road that is not there.

Output

Print qq lines. Line kk holds the answers after job kk, for city 1 to city nn in that order, separated by single spaces.

The answer for a city is the smallest number of roads on a route from that city to the capital. Print -1 for a city that cannot reach the capital.

Examples3

  1. Example 1

    Input
    5 6
1 2
1 3
2 4
2 5
3 5
4 5
5
2 1 2
1 1 4
2 2 4
2 2 5
1 1 2
    Expected output
    0 3 1 3 2
0 2 1 1 2
0 3 1 1 2
0 -1 1 1 2
0 1 1 1 2

  2. Example 2

    Input
    2 1
1 2
3
2 1 2
1 2 1
2 2 1
    Expected output
    0 -1
0 1
0 -1

  3. Example 3

    Input
    6 5
1 2
2 3
3 4
4 5
5 6
5
1 1 6
2 3 4
1 2 5
2 1 6
2 1 2
    Expected output
    0 1 2 3 2 1
0 1 2 3 2 1
0 1 2 3 2 1
0 1 2 3 2 3
0 -1 -1 -1 -1 -1