問題文

N 頂点からなる完全 DAG があります。つまり、このグラフの任意の頂点組 i, j \ (1 \leq i < j \leq N) には頂点 i から頂点 j への辺があり、また辺はそれらのみです。

M 個のクエリを順に処理してください。i 番目のクエリは以下の通りです。

• 頂点 X_i から Y_i への辺を削除する。その後、頂点 1 から頂点 Z_i への最短距離を求める。

制約

• 1 \leq N, M \leq 3 \times 10^5
• \displaystyle M \leq \frac{N(N - 1)}{2}
• 1 \leq X_i < Y_i \leq N
• 1 \leq Z_i \leq N
• (X_i, Y_i) \neq (X_j, Y_j) \ (i \neq j)
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (200 点) N \leq 1000
2. 追加の制約はない。

入力例 1

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

出力例 1

1
1
1
1
-1
-1

4 番目までのクエリでは、頂点 1 から頂点 Z_i への辺が残っているので答えは 1 である。それ以外のクエリでは頂点 Z_i に到達できないので、 -1 を出力する。

入力例 2

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

出力例 2

1
1
2
1
0
0
2
2
0
2