The country of IOI is a country consisting of $N$ cities. These cities are numbered $1, 2, \dots, N$. Professor JOI is interested in the process by which the road network of the country of IOI was developed.

After researching documents regarding the history of the country of IOI, Professor JOI found the following:

• The cities in the country of IOI have remained the same from immediately after the founding of the country until the present. Immediately after the founding of the country, there were no roads connecting the cities.
• $i$ years after the founding of the country ($1 \le i \le Q$), an improvement plan for the traffic conditions between city $A_i$ and city $B_i$ was proposed.
• Some of the proposed improvement plans were executed as planned, while others were abandoned without being executed.
• The documents clarify which improvement plans were executed.
• All executed improvement plans were completed within one year.

Furthermore, from another document, it was found that the improvement plan for the traffic conditions between city $A_i$ and city $B_i$ was as follows:

• If it is not possible to travel from city $A_i$ to city $B_i$ using the roads constructed at the time the improvement plan was proposed, a new road connecting city $A_i$ and city $B_i$ in both directions is constructed. The newly constructed road is unpaved.
• If it is possible to travel from city $A_i$ to city $B_i$ using the roads constructed at the time the improvement plan was proposed, all unpaved roads included in the path that uses the minimum number of roads are paved. If there are multiple paths that use the minimum number of roads, all unpaved roads in all such paths are paved in the same way. A road that has already been paved will not be paved again.

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

Task

Given the traffic condition improvement plans of the country of IOI and their execution status, write a program that calculates, for each improvement plan that was abandoned without being executed, how many roads would have been paved if that improvement plan had been executed.

Input

Read the following data from standard input:

• The first line contains two integers $N$ and $Q$, separated by a space. This indicates that there are $N$ cities in the country of IOI, and Professor JOI is focusing on the traffic condition improvement plans over $Q$ years since the founding of the country.
• The $i$-th line of the following $Q$ lines ($1 \le i \le Q$) contains three integers $T_i, A_i, B_i$, separated by spaces. The integer $T_i$ represents the execution status of the improvement plan proposed $i$ years after the founding of the country; $T_i = 1$ indicates that the improvement plan was executed, and $T_i = 2$ indicates that the improvement plan was abandoned without being executed. The integers $A_i$ and $B_i$ indicate that an improvement plan for the traffic conditions between city $A_i$ and city $B_i$ was proposed $i$ years after the founding of the country.

Output

For each improvement plan that was abandoned without being executed, output the number of roads that would be paved if that improvement plan were executed, on a single line. However, if a new road would be constructed by executing that improvement plan, output -1.

Constraints

All input data satisfy the following conditions:

• $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 \neq B_i$ ($1 \le i \le Q$).

Subtasks

Subtask 1 [10 points]

• $N \le 1\,000$.
• $Q \le 3\,000$.

Subtask 2 [25 points]

• There exists an integer $P$ ($1 \le P \le Q - 1$) such that $T_i = 1$ ($1 \le i \le P$) and $T_i = 2$ ($P + 1 \le i \le Q$).

Subtask 3 [25 points]

• For all $i$ ($1 \le i \le Q$) such that $T_i = 1$, one of the following holds:
  • Immediately before executing the improvement plan $i$ years after the founding, it is not possible to travel from city $A_i$ to city $B_i$ using the constructed roads.
  • Immediately before executing the improvement plan $i$ years after the founding, it is possible to travel from city $A_i$ to city $B_i$ using 200 or fewer of the constructed roads.

Subtask 4 [25 points]

• There are at most 200 values of $i$ ($1 \le i \le Q$) such that $T_i = 2$.

Subtask 5 [15 points]

• No additional constraints.

Examples

Input 1

3 7
1 1 2
2 2 1
2 2 3
1 2 1
2 1 2
1 2 3
2 1 3

Output 1

1
-1
0
1

Input 2

6 8
1 1 3
1 6 1
1 2 5
2 3 6
1 3 6
1 4 1
2 4 3
2 2 5

Output 2

2
1
1

Input 3

7 11
1 5 1
1 6 2
1 1 3
1 3 5
1 5 7
1 4 5
1 4 1
2 1 3
2 3 7
2 4 3
2 5 6

Output 3

0
1
0
-1