Road Development (Translated)

JOI Spring Training Camp 2014/15
Original Statement / Submission Site

Problem Statement

The country IOI consists of N cities numbered 1 through N. Professor JOI is interested in how the road network in IOI was developed.

From historical records, the following facts were discovered:

• The cities have remained unchanged since the founding of IOI. Initially, no roads existed.
• In year i (1 ≤ i ≤ Q), a road improvement plan between cities Ai and Bi was proposed.
• Some of these plans were executed, while others were abandoned.
• The records clearly show which plans were executed.
• Executed plans were completed within one year.

Details of each road improvement plan are as follows:

• If there is no path from Ai to Bi using existing roads, build a new unpaved bidirectional road between Ai and Bi.
• If a path already exists, then among the shortest paths (least number of roads), all unpaved roads on those paths are paved. If multiple such paths exist, all unpaved roads from all paths are paved. Already paved roads are not affected.

Professor JOI now wants to investigate the impact of each abandoned improvement plan. For each one, calculate how many roads would have been paved if that plan had been executed.

Task

Given the road improvement plans and their execution status, for each abandoned plan, determine how many roads would have been paved if the plan had been executed. If a new road would have been built, output -1 instead.

Input

The input consists of:

• The first line contains integers N and Q: the number of cities and the number of years (plans).
• Each of the next Q lines contains three integers Ti, Ai, Bi:
  • Ti = 1 means the plan was executed
  • Ti = 2 means the plan was abandoned
  • Ai and Bi are the cities involved in the plan in year i

Output

For each abandoned plan, output on a separate line the number of roads that would have been paved if the plan had been executed. Output -1 if a new road would have been built.

Constraints

• 2 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 300,000
• 1 ≤ Ti ≤ 2
• 1 ≤ Ai, Bi ≤ N

Subtasks

• Subtask 1 [10 points]: N ≤ 1,000, Q ≤ 3,000
• Subtask 2 [25 points]: All plans with Ti=1 come first, followed by all Ti=2
• Subtask 3 [25 points]: Every executed plan either:
  • connects previously unconnected cities, or
  • uses a path with ≤ 200 roads
• Subtask 4 [25 points]: There are at most 200 abandoned plans
• Subtask 5 [15 points]: No additional constraints

Sample 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

Sample Output 1

1
-1
0
1

Explanation of Sample Output 1

There are 3 cities in IOI. Initially, there were no roads. The road improvement plans were executed as follows:

• Year 1: A plan between cities 1 and 2 was executed.
  • At this point, there is no way to travel from city 1 to city 2, so a new road is built between them.
• Year 2: A plan between cities 2 and 1 was abandoned.
  • At this point, there is a way to travel from city 2 to city 1 using one road, and that road is still unpaved, so this plan would have paved that road. Therefore, the output is 1.
• Year 3: A plan between cities 2 and 3 was abandoned.
  • At this point, there is no way to travel from city 2 to city 3. Therefore, the output is -1.
• Year 4: A plan between cities 2 and 1 was executed.
  • At this point, there is a way to travel from city 2 to city 1 using one road, and that road is still unpaved, so that road is paved by this plan.
• Year 5: A plan between cities 1 and 2 was abandoned.
  • At this point, there is a way to travel from city 1 to city 2 using one road, and that road is already paved, so there is nothing left to pave. Therefore, the output is 0.
• Year 6: A plan between cities 2 and 3 was executed.
  • At this point, there is no way to travel from city 2 to city 3, so a new road was built between them.
• Year 7: A plan between cities 1 and 3 was abandoned.
  • At this point, there is a way to travel from city 1 to city 3 using two roads, and one of them is still unpaved, so this plan would have paved that road. Therefore, the output is 1.

Sample 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

Sample Output 2

2
1
1

Sample 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

Sample Output 3

0
1
0
-1