AT_hokudai_hitachi2019_1_a Problem A

本体不提供汉语翻译

[problemUrl]: https://atcoder.jp/contests/hokudai-hitachi2019-1/tasks/hokudai_hitachi2019_1_a

入力は以下の形式で与えられる。 > $ |V| $ $ |E| $ $ u_{1} $ $ v_{1} $ $ d_{u_{1},\ v_{1}} $ $ u_{2} $ $ v_{2} $ $ d_{u_{2},\ v_{2}} $ : $ u_{|E|} $ $ v_{|E|} $ $ d_{u_{|E|},\ v_{|E|}} $ $ T_{\max} $ $ \mathrm{info}_{0} $ $ \mathrm{info}_{1} $ : $ \mathrm{info}_{T_{\max}-1} $ - $ 1 $ 行目の $ |V| $ はグラフの頂点数、$ |E| $ はグラフの辺数を表す。 - 続く $ |E| $ 行で、グラフの辺が与えられる。 $ |E| $ 行のうち $ i $ 行目は、頂点 $ u_{i} $ と $ v_{i} $ の間に距離 $ d_{u_{i},\ v_{i}} $ の辺が存在することを表す。 - 続く $ 1 $ 行で、あなたが行動する時間の最大値 $ T_{\max} $ が与えられる。 続く行のうち $ \mathrm{info}_t $ は、時刻 $ t $ で発生する顧客からの注文の情報である。 $ \mathrm{info}_t $ は以下の形式で与えられる。 > $ N_{\text{new}} $ $ \mathrm{new\_id}_1 $ $ \mathrm{dst}_1 $ $ \mathrm{new\_id}_2 $ $ \mathrm{dst}_2 $ $ \vdots $ $ \mathrm{new\_id}_{N_{\text{new}}} $ $ \mathrm{dst}_{N_{\text{new}}} $ - $ N_{\text{new}} $ は、その時刻において新たに発生した注文の数を表す。 - 続く $ N_{\text{new}} $ 行で、新たに発生した注文情報が与えられる。$ i $ 番目に与えられる注文情報は、注文 ID が $ \mathrm{new\_{id}}_i $ であり、その注文の発生元 (お届け先) が頂点 $ \mathrm{dst}_i $ であることを表す。

以下の形式で標準出力に $ T_{\max} $ 行の整数を出力せよ。 > $ \mathrm{command}_{0} $ $ \mathrm{command}_{1} $ : $ \mathrm{command}_{T_{\max}-1} $ ただし、$ \mathrm{command}_{i} $ は以下のいずれかである。 #### `stay`: 車が動かない場合 ``` -1 ``` 車の位置は変わらない。 #### `move w`: 車を 頂点 $ w $ へ向けて $ 1 $ メートルすすめる場合 ``` w ``` ただし、車を動かす場合(`move w`)、出力は以下の条件を満たす必要がある。条件に違反している場合は `WA` (不正解) となる。 - $ w\ \in\ V $ - 車が頂点 $ u $ 上にいる場合、$ \left\{\ u,\ w\ \right\}\ \in\ E $ が成り立つ。 - 車が辺 $ \left\{\ u,\ v\ \right\} $ 上にいる場合、$ u\ =\ w $ または $ v\ =\ w $ が成り立つ。

### 問題概要 - **問題のねらい**: 本プログラミングコンテストは、買い物支援(配達)サービスの最適化をテーマとしている。本サービスを利用する顧客はそれぞれ異なる品物をお店に注文する（顧客からの注文には固有の$ \text{ID} $が割り振られる）。お店が利用できる車は一台のため、配達中に注文された商品については、お店に戻ってその商品を車に積んでから、顧客のもと商品を届けなければならない。 - **得点**: 最適化の目的は、制限時間 $ T_{\max} $ の間に「できるだけ多くの」商品を「できるだけ早く」顧客に届けることである。なお、注文は時刻 $ 0 $ から時刻 $ 0.95\ \times\ T_{\max} $ の間に発生する可能性がある。 - **諸制約**: 本コンテストでは、車に積むことのできる商品の数に制限はない。ただし、ある注文に対応する商品をお店まで取りに行き、車に積めるのは、**その商品が注文された以降の時刻に限る** ことに注意せよ。 - **問題 A**: この問題においては、注文が発生する時刻及び、注文がどの頂点で発生したかなど、注文に関する情報が事前に与えられる。 - **問題 B**: この問題においては、事前に注文に関する情報は与えられず、全ての注文は配達中にオンラインで発生する。  ### 時間・空間について - **時間**: $ t $ は $ 0\ \leq\ t\