P8495 [IOI 2022] Islands

Do not $\texttt{\#include "islands.h"}$.

Islands is a beautiful group of islands in the Java Sea. There are $N$ islands, numbered from $0$ to $N - 1$. There are $M$ canoes traveling between the islands, numbered from $0$ to $M - 1$. For all $i$ with $0 \le i \le M - 1$, canoe $i$ can dock at island $U_i$ or $V_i$, and can travel between islands $U_i$ and $V_i$. More specifically, when the canoe is docked at island $U_i$, you can use it to go from island $U_i$ to island $V_i$, after which the canoe becomes docked at island $V_i$. Similarly, when the canoe is docked at island $V_i$, it can sail from island $V_i$ to island $U_i$, after which the canoe becomes docked at island $U_i$. Initially, the canoe is docked at island $U_i$. There may be multiple canoes that can be used to travel between the same pair of islands. There may also be multiple canoes docked at the same island. For safety reasons, each canoe must be repaired after each trip, so the same canoe is not allowed to be used for two consecutive trips. That is, after using some canoe $i$, you must use some other canoe before you can use canoe $i$ again. Bu Dengklek wants to plan a journey among some islands. Her journey is **valid** if and only if it satisfies the following conditions: - Her journey must start at island $0$ and end at island $0$. - She must visit at least one island other than island $0$. - After the journey ends, every canoe must be docked at the same island where it was docked before the journey started. That is, for all $i$ with $0 \le i \le M - 1$, the canoe must be docked at island $U_i$. Help Bu Dengklek find a valid journey that uses at most $2\;000\;000$ trips, or tell her that no valid journey exists. It can be proven that under the constraints of this task (see the Constraints section), if a valid journey exists, then there also exists a valid journey with at most $2\;000\;000$ trips.

You need to implement the following function: ```go union(bool, int[]) find_journey(int N, int M, int[] U, int[] V) ``` - $N$: the number of islands. - $M$: the number of canoes. - $U$, $V$: two arrays of length $M$ that describe the islands connected by each canoe. - The function should return either a boolean or an integer array. - If no valid journey exists, the function should return `false`. - If a valid journey exists, you have two choices: - If you want to get full score, the function should return an array of at most $2\;000\;000$ integers that describes a valid journey. More precisely, the elements of the array should be the indices of the canoes used in the journey (in the order they are used). - If you want to get partial score, the function should return `true`, or return an array with more than $2\;000\;000$ integers, or return an integer array that does not describe a valid journey (see the “Subtasks” section for more details). - The function will be called exactly once.

### Example 1 Consider the following call: ```go find_journey(4, 5, [0, 1, 2, 0, 3], [1, 2, 3, 3, 1]) ``` The figure below shows the islands and canoes.  One possible valid journey is as follows. Bu Dengklek first uses canoes $0$, $1$, $2$, and $4$ in this order. As a result, she will be on island $1$. After that, Bu Dengklek can use canoe $0$ again, because the canoe is currently docked at island $1$, and the previous canoe she used was not $0$. After using canoe $0$ again, Bu Dengklek is now on island $0$. However, canoes $1$, $2$, and $4$ are not docked at the islands where they were docked before the journey started. Next, Bu Dengklek continues her journey, using canoes $3$, $2$, $1$, $4$, and using $3$ once again. Bu Dengklek returns to island $0$, and all canoes are docked at the same islands where they were docked before the journey started. Therefore, the return value $[0, 1, 2, 4, 0, 3, 2, 1, 4, 3]$ describes a valid journey. ### Example 2 Consider the following call: ```go find_journey(2, 3, [0, 1, 1], [1, 0, 0]) ``` The figure below shows the islands and canoes.  Bu Dengklek can only start by using canoe $0$, and then she can use canoe $1$ or $2$. Note that she cannot use canoe $0$ twice in a row. In both cases, Bu Dengklek returns to island $0$. However, there are canoes that are not docked at the islands where they were docked before the journey started, and after that Bu Dengklek cannot use any canoe anymore, because the only canoe docked at island $0$ is the one she just used. Since no valid journey exists, the function should return `false`.

### Constraints - $2 \le N \le 10^5$. - $1 \le M \le 2 \times 10^5$. - $0 \le U_i \le N - 1$ and $0 \le V_i \le N - 1$ (for all $i$ with $0 \le i \le M - 1$). - $U_i \neq V_i$ (for all $i$ with $0 \le i \le M - 1$). ### Subtasks 1. (5 points) $N = 2$. 1. (5 points) $N \le 400$. For every pair of distinct islands $x$ and $y$ ($0 \le x \lt y \le N - 1$), there are exactly two canoes that can travel between them. One of them is initially docked at island $x$, and the other is initially docked at island $y$. 1. (21 points) $N \le 1000$, $M$ is even, and for all **even** $i$ with $0 \le i \le M - 1$, canoes $i$ and $i + 1$ can both be used to travel between islands $U_i$ and $V_i$. Canoe $i$ is initially docked at island $U_i$, and canoe $i + 1$ is initially docked at island $V_i$. Formally, $U_i = V_{i + 1}$ and $V_i = U_{i + 1}$. 1. (24 points) $N \le 1000$, $M$ is even, and for all **even** $i$ with $0 \le i \le M - 1$, canoes $i$ and $i + 1$ can both be used to travel between islands $U_i$ and $V_i$. Both canoes are initially docked at island $U_i$. Formally, $U_i = U_{i + 1}$ and $V_i = V_{i + 1}$. 1. (45 points) No additional constraints. For each testcase where a valid journey exists, your solution: - gets full score if it returns a valid journey, - gets $35\%$ of the score if it returns `true`, or returns an array with more than $2\;000\;000$ integers, or returns an array that does not describe a valid journey, - scores $0$ in other cases. For each testcase where no valid journey exists, your solution: - gets full score if it returns `false`, - scores $0$ in other cases. Note that the final score for each subtask is the lowest score among all testcases in that subtask. ### Sample grader The sample grader reads input in the following format: - Line $1$: $N \; M$. - Line $2 + i$ ($0 \le i \le M - 1$): $U_i \; V_i$. The sample grader prints your output in the following format: - If `find_journey` returns a `bool`: - Line $1$: $0$. - Line $2$: $0$ if `find_journey` returns `false`, otherwise $1$. - If `find_journey` returns an `int[]`, and the elements of the array are $c[0], c[1], \ldots c[k-1]$, the sample grader prints: - Line $1$: $1$. - Line $2$: $k$. - Line $3$: $c[0] \; c[1] \; \ldots \; c[k-1]$. ### Notes In the statement, when the function interface is given, the generic type names `void`, `bool`, `int`, `int[]` (array), and `union(bool, int[])` are used. In C++, the grader will use appropriate data types or implementations, as shown in the table below: | `void ` | `bool` | `int` | `int[]` | | ------- | ------ | ------| ------------------ | | `void ` | `bool` | `int` | `std::vector` | | `union(bool, int[])` | Length of array `a` | | -------------------------------------- | ------------------- | | `std::variant` | `a.size()` | In C++, `std::variant` is defined in the header file ``. A function with return type `std::variant` can return either a `bool` or a `std::vector`. The following sample code shows three functions that return `std::variant`, and all of them work correctly: ```cpp std::variant foo(int N) { return N % 2 == 0; } std::variant goo(int N) { return std::vector(N, 0); } std::variant hoo(int N) { if (N % 2 == 0) { return false; } return std::vector(N, 0); } ``` Translated by ChatGPT 5