Note

The time limit for this problem is 5.000 seconds.

Problem Statement

There are $N$ people in a town, named person $1, 2, \cdots, N$.

Person $1$ has heard a rumor from someone in another town. Once a person learns this rumor, they never forget it.

When a person $A$ who knows the rumor talks with a person $B$ who does not know it, person $B$ newly learns the rumor. Nothing happens when two people who do not know the rumor talk with each other, or when two people who know the rumor talk with each other.

King Shobon is curious about how far the rumor has spread through the town. He has therefore tried to find out the past actions of the townspeople. Initially, King Shobon knows nothing about the past actions of the townspeople. King Shobon is not any of persons $1, 2, \cdots, N$.

A permutation $(P_1, P_2, \cdots, P_Q)$ of $(1,2,\cdots, Q)$ is given. Process the following $Q$ queries in order. King Shobon's knowledge of conversations accumulates across queries. That is, a conversation he learns about in a query remains known to him in all subsequent queries.

• In the $i$-th query, King Shobon learns that person $X_i$ and person $Y_i$ met and talked at time $P_i$. He then performs the following thought experiment: "Assuming that all the conversations I know about took place and no other conversations took place, how many people know the rumor at time $Q+1$?" The thought experiment does not affect the actual townspeople or later queries.

Constraints

• All inputs are integers.
• $2 \le N \le 4 \times 10^5$
• $1 \le Q \le 4 \times 10^5$
• $(P_1, P_2, \cdots, P_Q)$ is a permutation of $(1, 2, \cdots, Q)$.
• $1 \le X_i < Y_i \le N$ $(1 \le i \le Q)$

Input

$N$ $Q$
$P_1$ $X_1$ $Y_1$
$\vdots$
$P_Q$ $X_Q$ $Y_Q$

Output

Output $Q$ lines. On the $i$-th line $(1 \le i \le Q)$, output the answer to the thought experiment in the $i$-th query.

Sample

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

2
2
4
4
5