AT_pakencamp_2023_day2_f Make it incomplete

$ N $ 頂点からなる完全 DAG がある。つまり、このグラフの任意の頂点組 $ i, j \ (1 \leq i < j \leq N) $ には頂点 $ i $ から頂点 $ j $ への辺があり、また辺はそれらのみである。 $ M $ 個のクエリが順番に与えられるので答えよ。 $ i $ 番目のクエリは以下の通りである。 - 頂点 $ X_i $ から $ Y_i $ への辺を削除する。その後、頂点 $ 1 $ から頂点 $ Z_i $ への最短距離を求める。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ \vdots $ $ X_M $ $ Y_M $ $ Z_M $

$ M $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリの答えを出力せよ。ただし頂点 $ Z_i $ への到達が不可能な場合には `-1` を出力せよ。

### 配点 以下の小課題に点数が定められている。 1. ( $ 200 $ 点) $ N \leq 1000 $ 2. 追加の制約はない。 ### Sample Explanation 1 $ 4 $ 番目までのクエリでは、頂点 $ 1 $ から頂点 $ Z_i $ への辺が残っているので答えは `1` である。それ以外のクエリでは頂点 $ Z_i $ に到達できないので、 `-1` を出力する。 ### Constraints - $ 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) $ - 入力は全て整数