Road Development

IOI Country is a nation made up of $N$ cities. The cities are numbered $1, 2, \ldots, N$. Professor JOI became interested in how the road network of IOI Country was developed.

Professor JOI examined materials on the history of IOI Country and learned the following.

• The cities of IOI Country have been the same from right after its founding to the present. Right after the founding of IOI Country, there was not a single road connecting cities.
• In year $i$ after the founding of IOI Country ($1 \le i \le Q$), a plan to improve the traffic conditions between city $A_i$ and city $B_i$ was made.
• Some of the planned improvements were carried out as planned, while other plans were abandoned without being carried out.
• The materials make clear which improvement plans were carried out.
• Every improvement plan that was carried out was completed within one year.

From another document, Professor JOI learned that a plan to improve the traffic conditions between city $A_i$ and city $B_i$ works as follows.

• If city $B_i$ cannot be reached from city $A_i$ using roads already built at the time the improvement plan is made, a new road connecting city $A_i$ and city $B_i$ in both directions is built. The newly built road is unpaved.
• If city $B_i$ can be reached from city $A_i$ using roads already built at the time the improvement plan is made, then among all such routes, take one that uses the minimum number of roads and pave every unpaved road on it. If there are multiple routes using the minimum number of roads, pave the unpaved roads on all of them in the same way. A road that has already been paved is never paved again.

For further investigation, Professor JOI decided to compute, for each improvement plan that was abandoned without being carried out, how many roads would have been paved by that plan if only that plan had additionally been carried out.

Given the traffic improvement plans of IOI Country and whether each was carried out, write a program that computes, for each improvement plan that was abandoned without being carried out, how many roads would have been paved by that plan if it had been carried out.

Read the following data from standard input.

• The first line contains two integers $N$ and $Q$ separated by a space. This means that IOI Country has $N$ cities, and Professor JOI is looking at the traffic improvement plans over $Q$ years from the founding.
• Of the following $Q$ lines, the $i$-th line ($1 \le i \le Q$) contains three integers $T_i$, $A_i$, $B_i$ separated by spaces. The integer $T_i$ represents the status of the improvement plan made in year $i$ after the founding: $T_i = 1$ means the plan was carried out, and $T_i = 2$ means the plan was abandoned without being carried out. The integers $A_i$ and $B_i$ mean that in year $i$ after the founding, a plan to improve the traffic conditions between city $A_i$ and city $B_i$ was made.

For each improvement plan that was abandoned without being carried out, output on a single line the number of roads that would have been paved by that plan if it had been carried out. If carrying out that plan would build a new road, output -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$).