AT_ahc060_a [AHC060A] Ice Cream Collection

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.

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.

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 $ 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](https://img.atcoder.jp/ahc060/wX0NuJxV.html?lang=en&seed=0&output=sample)

### 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 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](https://en.wikipedia.org/wiki/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) - [Web version](https://img.atcoder.jp/ahc060/wX0NuJxV.html?lang=en): This is more powerful than the local version, providing animations. - [Local version](https://img.atcoder.jp/ahc060/wX0NuJxV.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc060/wX0NuJxV_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.