AT_ahc060_a [AHC060A] Ice Cream Collection

国中にアイスクリームの木が生えている Nihonbashi 国では、伝統のバニラと情熱のストロベリーの 2 つの味が至高とされる。 この国ではアイスの量よりも味の組み合わせの多様性が重視されており、いかにアイスを積み重ねるかが日々探求されている。 Nihonbashi 国にはアイスクリームの木とアイスクリームショップがそれぞれ複数存在し、道でつながったグラフ構造を構成している。 あなたはアイスクリーム職人として、このグラフ上を移動しながら、アイスクリームの木でアイスを収穫してコーンの上に積み上げていき、作成したアイスをアイスクリームショップに納品している。 各アイスクリームショップの満足度は、その店に並ぶ在庫の多様性、すなわち何種類の異なる組み合わせのアイスが提供されているかによって決まる。 現在、すべてのアイスクリームショップの在庫は空である。 あなたの使命は、Nihonbashi 国全体のアイスクリームショップの満足度の総和を最大化し、Nihonbashi 国に活気を取り戻すことである。

$ N $ 頂点 $ M $ 辺の連結な無向グラフがあり、頂点は $ 0, 1, \ldots, N-1 $ と番号づけられている。 $ i $ 本目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ。 各頂点は以下の2種類のいずれかである。 - アイスクリームショップ：頂点 $ 0, 1, \ldots, K-1 $ の計 $ K $ 個。 - アイスクリームの木：頂点 $ K, K+1, \ldots, N-1 $ の計 $ N-K $ 個。 アイスクリームの木には、収穫できるアイスの種類が設定されており、バニラ味のアイス（ White の `W` で表す）または、ストロベリー味のアイス（ Red の `R` で表す）を収穫できる。初期状態では、すべてのアイスクリームの木から、バニラ味のアイス（ `W` ）を収穫できる。 現在あなたは頂点 $ 0 $ （アイスクリームショップ）におり、手元には空のコーンを表す空文字列を持っている。あなたは以下のいずれかの行動を行うことを1ステップとし、最大で $ T $ ステップ繰り返す。 - 行動1: 現在位置の頂点から直接辺で繋がっている頂点の一つに移動し、移動先の頂点に応じてアイスの収穫または納品のどちらか1つを行う。移動先の頂点を $ v $ とする。 - 頂点 $ v $ がアイスクリームの木である場合：その木で現在収穫できるアイス（ `W` または `R` ）を収穫し、手元のコーンの末尾に追加する。 - 頂点 $ v $ がアイスクリームショップである場合：現在コーンに積み上げられているアイスの味の並びを表す文字列を、そのショップ $ v $ の在庫集合 $ S_v $ に追加する。その後、手元のコーンは空にする。コーンが空の状態で納品してもよい。その場合、空文字列が在庫集合に追加される。 - **制限事項：2回目以降の行動1では、行動1を前回行った時に移動元だった頂点には戻れない**。 具体的には、行動1で頂点 $ a $ から頂点 $ b $ へ移動したとして、（その間に行動2を行っていたとしても）次の行動1で頂点 $ a $ を移動先として指定することはできない。 - 行動2: この行動は、現在位置がバニラ味（ `W` ）のアイスクリームの木である場合にのみ行える。現在位置のアイスクリームの木にストロベリーの果汁を混ぜ込むことで、以降その木から収穫できるアイスの味をストロベリー味（ `R` ）に変更する。一度ストロベリー味になった木を、元のバニラ味に戻すことはできない。 入力生成方法に記載があるようにグラフは2-辺連結であるため、行動1は常に可能である。 各アイスクリームショップ $ v $ について、アイスクリームの在庫集合 $ S_v $ のサイズをできるだけ大きくせよ。 なお、すでにそのアイスクリームショップに納品された文字列と同じものを納品しても、集合のサイズは変化しないことに注意せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ T $ $ A_{0} $ $ B_{0} $ $ \vdots $ $ A_{M-1} $ $ B_{M-1} $ $ X_{0} $ $ Y_{0} $ $ \vdots $ $ X_{N-1} $ $ Y_{N-1} $ - 1行目には、4つの整数 $ N $ , $ M $ , $ K $ , $ T $ が与えられる。 $ N $ , $ M $ , $ K $ , $ T $ はそれぞれ、グラフの頂点数、辺数、アイスクリームショップの数、行動の最大回数を表し、 $ N = 100 $ , $ K = 10 $ , $ T = 10000 $ を満たす。 $ M $ のとる値については、入力生成方法を参照せよ。 - 続く $ M $ 行には、辺の情報が与えられる。辺 $ i $ は頂点 $ A_i $ と頂点 $ B_i $ を双方向に結ぶ。 - 続く $ N $ 行は、入力生成時に使用された頂点 $ i $ の座標が $ (X_i, Y_i) $ として与えられる。座標の値は整数であり、 $ 0 \leq X_i, Y_i \leq 300, (X_i, Y_i) \neq (X_j, Y_j)\ (i \neq j) $ を満たす。不要であれば読み込まなくても構わない。

以下のフォーマットで $ T $ 行以下出力せよ。 - 行動1を行う場合 移動先の頂点番号 $ v $ を出力せよ。 > $ v $ - 行動2を行う場合 `-1` を出力せよ。 ``` -1 ``` [例を見る](https://img.atcoder.jp/ahc060/wX0NuJxV.html?lang=ja&seed=0&output=sample)

### 得点 各アイスクリームショップ $ i $ $ (0 \le i \lt K) $ における在庫集合 $ S_i $ のサイズの合計 $ \sum_{i=0}^{K-1} |S_i| $ が得点として得られる。 以下に挙げる不正な出力をした場合、WAと判定される。 - 現在位置の頂点がバニラ味のアイスクリームの木でない場合に、行動2を行う。 - 行動1で指定した頂点が現在位置の頂点から直接辺で繋がっていない。 - 2回目以降の行動1で、行動1を前回行った時の移動元だった頂点に移動する。 - 行動回数が $ T $ 回を超える。 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数を $ \mathrm{rand}(L,U) $ で表す。 1. 各頂点 $ i $ の座標 $ (X_i, Y_i) $ を、 $ X_i = \mathrm{rand}(0, 300) $ , $ Y_i = \mathrm{rand}(0, 300) $ で選ぶ。ただし、既に生成された他の頂点とのユークリッド距離が $ 20 $ 以下となる場合は選び直す。これを $ N $ 個繰り返し、頂点集合 $ V $ を得る。 2. 得られた頂点集合 $ V $ に対して、[ドロネー三角形分割](https://ja.wikipedia.org/wiki/%E3%83%89%E3%83%AD%E3%83%8D%E3%83%BC%E5%9B%B3)を計算し、その三角形分割の辺を $ E $ とする。 3. $ E $ の各辺をランダムに並べ替え、順に次の操作を行う： - 「その辺を取り除いてもグラフ $ (V, E) $ が $ 2 $ -辺連結かつ関節点が存在しない」場合、確率 $ 0.7 $ でその辺を $ E $ から取り除く。 4. 全ての辺について処理を終えた後の $ E $ をグラフの辺集合とする。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc060/wX0NuJxV.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc060/wX0NuJxV.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc060/wX0NuJxV_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。