{"raw_statement":[{"iden":"background","content":"不要 $\\texttt{\\#include \"islands.h\"}$。"},{"iden":"statement","content":"千岛是爪哇海里一组美丽的岛屿，其中有 $N$ 个岛屿，编号为从 $0$ 到 $N - 1$。\n\n有 $M$ 艘独木舟在岛屿之间航行，编号为从 $0$ 到 $M - 1$。对于满足 $0 \\le i \\le M - 1$ 的所有 $i$，独木舟 $i$ 可以停靠在岛屿 $U_i$ 或 $V_i$，并且在岛屿 $U_i$ 和 $V_i$ 之间航行。具体来说，当独木舟停靠在岛屿 $U_i$ 时，可以用它从岛屿 $U_i$ 去往岛屿 $V_i$，此后该独木舟就变成停靠在岛屿 $V[i]$。类似地，当该独木舟停靠在岛屿 $V[i]$ 时，它可以从岛屿 $V_i$ 航向岛屿 $U_i$，此后该独木舟就变成停靠在岛屿 $U_i$。在初始时，该独木舟停靠在岛屿 $U_i$。可能有多艘独木舟能用于在同一对岛屿之间航行。也可能会有多艘独木舟停靠在同一个岛屿处。\n\n出于安全考虑，各艘独木舟在每次航行后必须进行维修，因此同一独木舟不允许紧接着完成两次航行。也就是说，在用完某艘独木舟 $i$ 后，必须先用过另外某艘独木舟，才能再启用独木舟 $i$。\n\nBu Dengklek 想策划一次在部分岛屿之间的旅行。她的旅程是**合理的**，当且仅当满足如下条件：\n\n- 她的旅程应从岛屿 $0$ 开始，并且在该岛屿结束。\n- 她应该游览岛屿 $0$ 之外的至少一个岛屿。\n- 在旅行结束后，每艘独木舟应停靠在旅行开始前它所在的岛屿。也就是说，对于满足 $0 \\le i \\le M - 1$ 的所有 $i$，独木舟必须停靠在岛屿 $U_i$。\n\n请你帮助 Bu Dengklek 找出包括至多航行 $2\\;000\\;000$ 次的合理旅行，或者告诉她不存在合理旅行。\n可以证明，在本题所给出的约束条件下（参见约束条件部分），如果存在合理旅行，则必然存在航行次数不超过 $2\\;000\\;000$ 次的合理旅行。"},{"iden":"input","content":"你要实现如下函数：\n\n```go\nunion(bool, int[]) find_journey(int N, int M, int[] U, int[] V)\n```\n\n- $N$：岛屿数量。\n- $M$：独木舟数量。\n- $U$, $V$：长度为 $M$ 的两个数组，给出独木舟航行的岛屿。\n- 该函数应当返回一个布尔类型或者整数数组。\n  - 如果不存在合理旅程，该函数应返回 `false`。\n  - 如果存在合理旅程，你有两个选择：\n  - 如果想得到全部的分数，该函数应返回一个至多包含 $2\\;000\\;000$ 个整数的数组，该数组用来刻画一个合理旅程。更确切地说，该数组中的元素应为旅程中所用独木舟的编号（按照独木舟的使用顺序）。\n  - 如果想得到部分分数，该函数应返回 `true`，或返回一个包含超过 $2\\;000\\;000$ 个整数的数组，或返回了一个未给出合理旅程的整数数组（更多细节参见“子任务”部分）。\n- 该函数将被调用恰好一次。"},{"iden":"output","content":"### 例子 1\n\n考虑如下调用：\n\n```go\nfind_journey(4, 5, [0, 1, 2, 0, 3], [1, 2, 3, 3, 1])\n```\n\n下图给出了岛屿和独木舟。\n\n![](https://arina.loli.net/2022/08/12/Aey1En5QvcFHrUZ.png)\n\n一个可行的合理旅行如下。Bu Dengklek 先依次使用独木舟 $0$，$1$，$2$ 和 $4$。结果是她将在岛屿 $1$ 上。其后，Bu Dengklek 可以再次使用独木舟 $0$，因为该独木舟正停靠在岛屿 $1$，而且她用的上一艘独木舟不是 $0$。再次使用独木舟 $0$ 后，现在 Bu Dengklek 在岛屿 $0$ 上。然而，独木舟 $1$，$2$ 和 $4$ 没有停靠在旅程开始前它们所在的岛屿。接下来 Bu Dengklek 继续她的旅程，使用独木舟 $3$，$2$，$1$，$4$ 和再一次使用 $3$。Bu Dengklek 回到了岛屿 $0$ 上，并且所有独木舟都停靠在旅行开始前它们所在的岛屿。\n\n因此，返回结果 $[0, 1, 2, 4, 0, 3, 2, 1, 4, 3]$ 刻画了一个合理旅程。\n\n### 例子 2\n\n考虑如下调用：\n\n```go\nfind_journey(2, 3, [0, 1, 1], [1, 0, 0])\n```\n\n下图给出了岛屿和独木舟。\n\n![](https://arina.loli.net/2022/08/12/nWJqhN7KXV3FPRl.png)\n\nBu Dengklek 仅能从使用独木舟 $0$ 开始，此后她可以使用独木舟 $1$ 或者 $2$。注意，她不能连续使用独木舟 $0$ 两次。在两种情况下，Bu Dengklek 都回到了岛屿 $0$ 上。然而，有独木舟没停靠在旅行开始前它们所在的岛屿，而 Bu Dengklek 此后却无法再使用任何独木舟，因为唯一停靠在岛屿 $0$ 的独木舟是她刚用过的那艘。由于不存在合理旅程，该函数应当返回 `false`。"},{"iden":"note","content":"### 约束条件\n\n- $2 \\le N \\le 10^5$；\n- $1 \\le M \\le 2 \\times 10^5$；\n- $0 \\le U_i \\le N - 1$ 且 $0 \\le V_i \\le N - 1$（对于所有满足 $0 \\le i \\le M - 1$ 的 $i$）；\n- $U_i \\neq V_i$（对于所有满足 $0 \\le i \\le M - 1$ 的 $i$）。\n\n### 子任务\n\n1. （5 分）$N = 2$。\n1. （5 分） $N \\le 400$。\n   对于每一对不同的岛屿 $x$ 和 $y$（$0 \\le x \\lt y \\le N - 1$），恰好有两艘可在它们之间航行的独木舟。\n   其中一艘停靠在岛屿 $x$，而另一艘停靠在岛屿 $y$。\n1. （21 分） $N \\le 1000$，$M$ 是偶数，而且对于满足 $0 \\le i \\le M - 1$ 的所有**偶数** $i$，独木舟 $i$ 和 $i + 1$ 都可以用于在岛屿 $U_i$ 和 $V_i$ 之间航行。独木舟 $i$ 最初停靠在岛屿 $U_i$ 处，而独木舟 $i + 1$ 最初停靠在岛屿 $V_i$ 处。形式化地，$U_i = V_{i + 1}$ 且 $V_i = U_{i + 1}$。\n1. （24 分） $N \\le 1000$，$M$ 是偶数，而且对于满足 $0 \\le i \\le M - 1$ 的所有**偶数** $i$，独木舟 $i$ 和 $i + 1$ 都可以用于在岛屿 $U_i$ 和 $V_i$ 之间航行。两艘独木舟最初都停靠在岛屿 $U_i$ 处。\n   形式化地，$U_i = U_{i + 1}$ 且 $V_i = V_{i + 1}$。\n1. （45 分）没有额外的约束条件。\n\n对于每个存在合理旅程的测试用例，你的解答：\n\n- 如果返回一个合理旅程，将得到全部分数，\n- 如果返回 `true`，或返回一个超过 $2\\;000\\;000$ 个整数的数组，或返回一个未给出合理旅程的数组，将得到 $35\\%$ 的分数，\n- 在其他情况下得分为 $0$。\n\n对于每个不存在合理旅程的测试用例，你的解答：\n\n- 如果返回 `false`，将得到全部分数，\n- 在其他情况下得分为 $0$。\n\n注意，每个子任务上的最终得分，为该子任务中所有测试用例上的最低得分。\n\n### 评测程序示例\n\n评测程序示例读取如下格式的输入：\n\n- 第 $1$ 行：$N \\; M$；\n- 第 $2 + i$ 行（$0 \\le i \\le M - 1$）：$U_i \\; V_i$。\n\n测试程序示例将按照如下格式打印你的答案：\n\n- 如果 `find_journey` 返回一个 `bool`：\n  - 第 $1$ 行：$0$；\n  - 第 $2$ 行：如果 `find_journey` 返回 `false` 则为 $0$，否则为 $1$。\n- 如果 `find_journey` 返回一个 `int[]`，该数组中的元素记为 $c[0], c[1], \\ldots c[k-1]$。测试程序示例打印出：\n  - 第 $1$ 行：$1$；\n  - 第 $2$ 行：$k$；\n  - 第 $3$ 行：$c[0] \\; c[1] \\; \\ldots \\; c[k-1]$。\n\n### 约定\n\n题面在给出函数接口时，会使用一般性的类型名称 `void`、`bool`、`int`、`int[]`（数组）和 `union(bool, int[])`。\n\n在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：\n\n| `void ` | `bool` | `int` | `int[]`            |\n| ------- | ------ | ------| ------------------ |\n| `void ` | `bool` | `int` | `std::vector<int>` |\n\n| `union(bool, int[])`                   | 数组 `a` 的长度 |\n| -------------------------------------- | ------------------- |\n| `std::variant<bool, std::vector<int>>` | `a.size()`          |\n\nC++ 语言里，`std::variant` 定义在 `<variant>` 头文件中。\n一个返回类型为 `std::variant<bool, std::vector<int>>` 的函数可以返回一个 `bool` 或一个 `std::vector<int>`。\n以下示例代码给出了三个返回 `std::variant` 的函数，它们都能正常工作：\n\n```cpp\nstd::variant<bool, std::vector<int>> foo(int N) {\n    return N % 2 == 0;\n}\n\nstd::variant<bool, std::vector<int>> goo(int N) {\n    return std::vector<int>(N, 0);\n}\n\nstd::variant<bool, std::vector<int>> hoo(int N) {\n    if (N % 2 == 0) {\n        return false;\n    }\n\n    return std::vector<int>(N, 0);\n}\n```"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}