AT_bogosortcontest_div2_n Optimal Search

jastaway くんは次のインタラクティブな問題を解いています。 > ジャッジは $ N $ 頂点 $ M $ 辺の正の重み付き有向グラフを隠し持っています。各辺には順番に $ 1 $ から $ M $ までの番号が振られています。 また、グラフには自己ループや多重辺が存在することがあります。 > > jastaway くんは最初頂点 $ 1 $ にいて、頂点 $ N $ までの最短距離を求めたいです。 最初に与えられるのは、頂点数 $ N $ と頂点 $ 1 $ の出次数 $ \operatorname{deg}(1) $ です。初期状態では頂点 $ 1 $ のみが発見済みです。 > > 以下のクエリを、好きな順番で行うことができます。 > > - **クエリ $ 1 $** : 現在 jastaway くんがいる頂点を $ u $ とします。 $ 1 \leq i \leq \operatorname{deg}(u) $ を満たす整数 $ i $ を選び、 $ u $ から出る辺のうち、辺番号が小さい方から数えて $ i $ 番目の辺の情報を得ます。具体的には、その辺の行き先の頂点 $ v $ と辺の重み $ w $ が与えられます。その後、頂点 $ v $ が発見済みでなければ、新たに発見済みになります。 > - **クエリ $ 2 $** : 発見済みの頂点 $ u $ に jastaway くんが移動します。その後、頂点 $ u $ の出次数 $ \operatorname{deg}(u) $ が与えられます。 > > jastaway くんが探索を終了したと宣言して最短距離 $ X $ を出力した後、ジャッジは、これまでのクエリ結果に矛盾しない範囲で辺の行き先や重みを自由に変えたり、辺を削除・追加したりして反例となるグラフを作ることができます。 どのようにグラフを変えられても、これまでの情報だけで頂点 $ 1 $ から $ N $ までの実際の最短距離が $ X $ で確定している場合のみ正答となります。 > > 最短距離を正しく確定できるクエリ列のうち、クエリ $ 1 $ の操作回数が最小となるようにクエリを行ってください。 ジャッジが初めに持っているグラフの辺の重みは $ 10 $ の倍数ですが、ジャッジが変えた後のグラフの辺の重みは $ 1 $ 以上 $ 10^9 $ 以下の整数すべてを許します。 あなたには、初期のグラフと、 jastaway くんが実際に行った長さ $ Q $ のクエリの履歴、そして jastaway くんが最終的に出力した最短距離 $ X $ が与えられます。 jastaway くんの解答をジャッジしてください。ただし、 jastaway くんは不正な出力は行わないことが保証されています。 - 反例となるグラフが存在する場合は `WA` と出力してください。 jastaway くんはなぜ間違っているのかも知りたいので、反例となるグラフも出力してください。 - 最短距離 $ X $ が正しく、反例となるグラフが存在しないが、クエリ $ 1 $ の回数が最小でない場合は `TOOMANY` と出力してください。 - 上記のいずれでもない場合は `AC` と出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \vdots $ $ u_M $ $ v_M $ $ w_M $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ $ X $ ジャッジが初めに持っているグラフの $ k $ 番目の辺は、頂点 $ u_k $ から頂点 $ v_k $ へ向かう重み $ w_k $ の有向辺である。 各 $ \mathrm{query}_j $ は以下のいずれかの形式で与えられる。 > $ 1 $ $ i $ これは、 jastaway くんの $ j $ 番目のクエリがクエリ $ 1 $ であり、現在いる頂点から出る辺のうち（入力で与えられた順で） $ i $ 番目の辺を探索したことを意味する。 > $ 2 $ $ u $ これは、 jastaway くんの $ j $ 番目のクエリがクエリ $ 2 $ であり、頂点 $ u $ に移動したことを意味する。

$ 1 $ 行目に判定結果（`AC`, `TOOMANY`, `WA` のいずれか）を出力せよ。 判定結果が `WA` の場合、続けて反例となるグラフを以下の形式で出力せよ。 > $ M' $ $ u'_1 $ $ v'_1 $ $ w'_1 $ $ \vdots $ $ u'_{M'} $ $ v'_{M'} $ $ w'_{M'} $ ここで、 $ M' $ は辺の本数を、 $ u^{'}_k, v^{'}_k, w^{'}_k $ は $ k $ 番目の辺が頂点 $ u^{'}_k $ から頂点 $ v^{'}_k $ へ向かう重み $ w^{'}_k $ の有向辺であることを意味する 反例となるグラフは以下の条件をすべて満たす必要がある。 - $ 1 \leq M' \leq 5 \times 10^5 $ - $ 1 \leq u'_k, v'_k \leq N \ (1 \leq k \leq M') $ - $ 1 \leq w'_k \leq 10^9 \ (1 \leq k \leq M') $ - 頂点 $ 1 $ から頂点 $ N $ へ到達可能である - 頂点 $ 1 $ から頂点 $ N $ への最短距離が入力の $ X $ と異なる - 入力で与えられる jastaway くんのクエリの履歴に矛盾しない（反例となるグラフ上でクエリを順に処理しても、ジャッジが jastaway くんに返す結果が同じである）

### Sample Explanation 1 すべての頂点と辺をクエリ $ 1 $ で探索しているため、反例を作ることはできません。 また、 $ 4 $ 回未満のクエリ $ 1 $ の回数で最短距離を正しく確定することはできないため、 `AC` が答えとなります。 ### Sample Explanation 2 辺 $ 2 $ の重みを $ 1 $ に変えても jastaway くんのクエリ履歴に矛盾せず、最短距離が $ 1 $ になるので、反例となるグラフが作れます。 ### Constraints - $ 2 \leq N \leq 10^5 $ - $ 1 \leq M \leq 10^5 $ - $ 0 \leq Q \leq 10^6 $ - $ 1 \leq u_k, v_k \leq N \ (1 \leq k \leq M) $ - $ 10 \leq w_k \leq 10^9 \ (1 \leq k \leq M) $ - $ w_k $ は $ 10 $ の倍数である - 頂点 $ 1 $ から頂点 $ N $ へ到達可能である - $ 1 \leq X \leq 10^{16} $ - 不正なクエリは入力されない - 入力される数値はすべて整数