注意

この問題の実行時間制限は 5.000 秒です。

問題文

街に $N$ 人がおり、それぞれ人 $1, 2, \cdots, N$ と名前がついています。

人 $1$ は他の街にいる人からうわさ話を聞きつけました。このうわさ話は一度知ると忘れることはありません。

うわさ話を知っている人 $A$ とうわさ話を知らない人 $B$ が会話をすると、人 $B$ はうわさ話を新たに知ることになります。うわさ話を知らない人同士や、うわさ話を知っている人同士が会話をしても何も起こりません。

しょぼん王はうわさ話がどのくらい街中に広がったかが気になっています。そのため、街の人々の過去の行動を把握しようとしました。最初、しょぼん王は街の人々の過去の行動を全く把握していません。また、しょぼん王は人 $1, 2, \cdots, N$ のいずれでもありません。

$(1,2,\cdots, Q)$ の順列 $(P_1, P_2, \cdots, P_Q)$ が与えられます。次の $Q$ クエリを順に処理してください。しょぼん王の会話に関する知識はクエリを通して蓄積されます。すなわち、各クエリでしょぼん王が知った会話は以降のクエリでも知っているものとします。

• $i$ 番目のクエリでは、しょぼん王は時刻 $P_i$ に人 $X_i$ と人 $Y_i$ が会って会話をしたことを知る。その後、しょぼん王は次の思考実験を行った：「しょぼん王の知っている会話がすべて行われ、かつそれら以外の会話が行われなかったと仮定した場合に、時刻 $Q+1$ の時点でうわさ話を知っている人数はどのくらいか？」。なお、思考実験によって、実際の街の人々や後のクエリに影響を与えない。

制約

• 入力はすべて整数
• $2 \le N \le 4 \times 10^5$
• $1 \le Q \le 4 \times 10^5$
• $(P_1, P_2, \cdots, P_Q)$ は $(1, 2, \cdots, Q)$ の順列である
• $1 \le X_i < Y_i \le N$ $(1 \le i \le Q)$

入力

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

出力

$Q$ 行出力せよ。 $i$ 行目 $(1 \le i \le Q)$ には、 $i$ 番目のクエリの思考実験における答えを出力せよ。

サンプル

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

2
2
4
4
5