A - Ice Cream Collection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

ストーリー

国中にアイスクリームの木が生えている 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 のサイズをできるだけ大きくせよ。
なお、すでにそのアイスクリームショップに納品された文字列と同じものを納品しても、集合のサイズは変化しないことに注意せよ。

得点

各アイスクリームショップ 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 となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。

入力

入力は以下の形式で標準入力から与えられる。

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

例を見る

入力生成方法

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 に対して、ドロネー三角形分割を計算し、その三角形分割の辺を E とする。
  3. E の各辺をランダムに並べ替え、順に次の操作を行う：
    • 「その辺を取り除いてもグラフ (V, E) が 2-辺連結かつ関節点が存在しない」場合、確率 0.7 でその辺を E から取り除く。
  4. 全ての辺について処理を終えた後の E をグラフの辺集合とする。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

Story

In the Kingdom of Nihonbashi, there are many "ice cream trees." Two flavors are famous here: Traditional Vanilla and Passionate Strawberry. People in this country value the variety of flavor combinations more than the total amount of ice cream.

The kingdom is a graph with vertices and edges. These vertices represent either ice cream trees or ice cream shops. As an ice cream maker, you move around this graph, harvest flavors from trees to stack them on your cone, and deliver the completed ice cream to the shops.

A shop's satisfaction is determined by the diversity of its inventory — how many different flavor combinations it has. Right now, all shops are empty. Your mission is to maximize the total satisfaction of all ice cream shops to make the kingdom lively again.

Problem Statement

There is a connected undirected graph with N vertices and M edges. The vertices are numbered 0, 1, \ldots, N-1. The i-th edge connects vertex A_i and vertex B_i.

Each vertex is one of the following two types:

  • Ice Cream Shops: Vertices 0, 1, \ldots, K-1 (K vertices in total).
  • Ice Cream Trees: Vertices K, K+1, \ldots, N-1 (N-K vertices in total).

Each ice cream tree provides a specific flavor: Vanilla (W = White) or Strawberry (R = Red). Initially, all ice cream trees provide Vanilla (W).

You start at vertex 0 (an ice cream shop) with an empty cone (represented by an empty string). You can perform up to T steps. In each step, choose one of the following two actions:

  • Action 1: Move from your current vertex to an adjacent vertex v. Then, depending on the type of v, either harvest ice cream or make a delivery.
    • If v is an ice cream tree: Harvest the current flavor (W or R) from that tree and add it to the end of your cone's string.
    • If v is an ice cream shop: Add the current flavor string on your cone to the shop's inventory set S_v. Then, your cone becomes empty. You may deliver an empty string; in this case, the empty string is added to the inventory set S_v.
    • Restriction: You cannot move back to the vertex you just came from in your previous Action 1. Specifically, if your last Action 1 was moving from vertex a to vertex b, your next Action 1 cannot be moving from b back to a (even if you performed Action 2 in between).
  • Action 2: This action can only be performed if your current position is a Vanilla (W) ice cream tree. By adding strawberry juice, the flavor harvested from this tree changes to Strawberry (R) for all future harvests. You cannot change a Strawberry tree back to Vanilla.

As described in the Input Generation, the graph is 2-edge-connected, so Action 1 is always possible.

Maximize the size of the inventory set S_v for each ice cream shop v. Note that delivering a string that is already in S_v does not increase the size of the set.

Scoring

Your score is the sum of the sizes of the inventory sets S_i across all ice cream shops i (0 \le i \lt K): \sum_{i=0}^{K-1} |S_i|

If the following invalid outputs are produced, it will be judged as WA.

  • You perform Action 2 when your current vertex is not a Vanilla (W) ice cream tree.
  • In Action 1, you specify a vertex that is not directly connected to your current vertex by an edge.
  • In Action 1 (from the second time onwards), you move to the vertex from which you departed in the previous Action 1.
  • The total number of actions exceeds T.

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE, and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input

Input is given from Standard Input in the following format:

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}
  • The first line contains four integers N, M, K, T. These represent the number of vertices, the number of edges, the number of ice cream shops, and the maximum number of actions, respectively. These values satisfy N = 100, K = 10, and T = 10000. For the value of M, please refer to the "Input Generation" section.
  • The following M lines provide information about the edges. Edge i bi-directionally connects vertex A_i and vertex B_i.
  • The following N lines provide the coordinates (X_i,Y_i) of each vertex i used during input generation. These coordinates are integers satisfying 0 \leq X_i, Y_i \leq 300 and (X_i, Y_i) \neq (X_j, Y_j) for any i \neq j. You may skip reading them if you don't need them.

Output

Output T or fewer lines in the following format:

  • To perform Action 1: Output the vertex index v of the destination.
v
  • To perform Action 2: Output -1.
-1

Show example

Input Generation

Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive.

  1. For each vertex i, the coordinates (X_i,Y_i) are chosen as X_i = \mathrm{rand}(0, 300), Y_i = \mathrm{rand}(0, 300). If the Euclidean distance to any already generated vertex is 20 or less, the coordinates are re-selected. This process is repeated N times to obtain the vertex set V.
  2. Compute the Delaunay Triangulation for the vertex set V, and let the resulting set of edges be E.
  3. Randomly shuffle the edges of E, and perform the following operation on each edge in order:
    • If removing the edge keeps the graph (V,E) 2-edge-connected and free of articulation points, the edge is removed from E with a probability of 0.7.
  4. The set E after processing all edges becomes the edge set of the graph.

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.