AT_game_h Lexicographic Order Game

$ N $ 頂点 $ M $ 辺の有向グラフがあります。頂点には頂点 $ 1 $ から頂点 $ N $ までの番号が付いており、 $ i $ 番目の辺 $ (1\le i\le M) $ は頂点 $ u_i $ から頂点 $ v_i $ へ向かう辺で英小文字 $ c_i $ が書かれています。また、どの頂点も出次数が $ 1 $ 以上であることが保証されます。 Alice と Bob がこのグラフを使って以下のようなゲームを行います。 - はじめ、コマが頂点 $ 1 $ に置かれている。また、空文字列 $ S $ を用意する。 - $ k=1,2,\ldots,2K $ の順に、 $ k $ が奇数なら Alice が、偶数なら Bob が以下の操作を行う： - 現在コマが置かれている頂点を $ u_i $ とする辺 $ i $ を $ 1 $ 本選び、コマを頂点 $ v_i $ に動かす。その後、 $ S $ の**先頭**に文字 $ c_i $ を連結する。 Alice は最終的な $ S $ を辞書順でできるだけ小さく、Bob はできるだけ大きくしたいです。 両者が最善を尽くしたときの最終的な $ S $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ u_1 $ $ v_1 $ $ c_1 $ $ u_2 $ $ v_2 $ $ c_2 $ $ \vdots $ $ u_M $ $ v_M $ $ c_M $

両者が最善を尽くしたときの最終的な $ S $ を出力せよ。

### Sample Explanation 1 両者が最善を尽くしたとき、ゲームは以下のように進行します： - Alice の手番：辺 $ 1 $ を選び、コマを頂点 $ 1 $ から頂点 $ 2 $ に動かす。 $ S= $ `a` となる。 - Bob の手番：辺 $ 2 $ を選び、コマを頂点 $ 2 $ から頂点 $ 3 $ に動かす。 $ S= $ `ba` となる。 - Alice の手番：辺 $ 5 $ を選び、コマを頂点 $ 3 $ から頂点 $ 2 $ に動かす。 $ S= $ `eba` となる。 - Bob の手番：辺 $ 4 $ を選び、コマを頂点 $ 2 $ から頂点 $ 1 $ に動かす。 $ S= $ `deba` となる。 最終的な $ S $ は `deba` となります。 ### Constraints - $ 1\le N\le 10^2 $ - $ N\le M\le 10^3 $ - $ 1\le K\le 10^4 $ - $ 1\le u_i,v_i\le N $ - $ c_i $ は英小文字 - $ (u_i,v_i,c_i) \neq (u_j,v_j,c_j) $ $ (i\neq j) $ - $ x=1,2,\ldots,N $ に対し $ u_i=x $ を満たす $ i $ が存在する