注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "islands.h"。

题目描述

千岛是爪哇海里一组美丽的岛屿，其中有 $N$ 个岛屿，编号为从 $0$ 到 $N - 1$。

有 $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$。可能有多艘独木舟能用于在同一对岛屿之间航行。也可能会有多艘独木舟停靠在同一个岛屿处。

出于安全考虑，各艘独木舟在每次航行后必须进行维修，因此同一独木舟不允许紧接着完成两次航行。也就是说，在用完某艘独木舟 $i$ 后，必须先用过另外某艘独木舟，才能再启用独木舟 $i$。

Bu Dengklek 想策划一次在部分岛屿之间的旅行。她的旅程是合理的，当且仅当满足如下条件：

• 她的旅程应从岛屿 $0$ 开始，并且在该岛屿结束。
• 她应该游览岛屿 $0$ 之外的至少一个岛屿。
• 在旅行结束后，每艘独木舟应停靠在旅行开始前它所在的岛屿。也就是说，对于满足 $0 \le i \le M - 1$ 的所有 $i$，独木舟必须停靠在岛屿 $U_i$。

请你帮助 Bu Dengklek 找出包括至多航行 $2\;000\;000$ 次的合理旅行，或者告诉她不存在合理旅行。 可以证明，在本题所给出的约束条件下（参见约束条件部分），如果存在合理旅行，则必然存在航行次数不超过 $2\;000\;000$ 次的合理旅行。

实现细节

你要实现如下函数：

union(bool, int[]) find_journey(int N, int M, int[] U, int[] V)

• $N$：岛屿数量。
• $M$：独木舟数量。
• $U$, $V$：长度为 $M$ 的两个数组，给出独木舟航行的岛屿。
• 该函数应当返回一个布尔类型或者整数数组。
  • 如果不存在合理旅程，该函数应返回 false。
  • 如果存在合理旅程，你有两个选择：
  • 如果想得到全部的分数，该函数应返回一个至多包含 $2\;000\;000$ 个整数的数组，该数组用来刻画一个合理旅程。更确切地说，该数组中的元素应为旅程中所用独木舟的编号（按照独木舟的使用顺序）。
  • 如果想得到部分分数，该函数应返回 true，或返回一个包含超过 $2\;000\;000$ 个整数的数组，或返回了一个未给出合理旅程的整数数组（更多细节参见“子任务”部分）。
• 该函数将被调用恰好一次。

样例 1

考虑如下调用：

find_journey(4, 5, [0, 1, 2, 0, 3], [1, 2, 3, 3, 1])

下图给出了岛屿和独木舟。

一个可行的合理旅行如下。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$ 上，并且所有独木舟都停靠在旅行开始前它们所在的岛屿。

因此，返回结果 $[0, 1, 2, 4, 0, 3, 2, 1, 4, 3]$ 刻画了一个合理旅程。

样例 2

考虑如下调用：

find_journey(2, 3, [0, 1, 1], [1, 0, 0])

下图给出了岛屿和独木舟。

Bu Dengklek 仅能从使用独木舟 $0$ 开始，此后她可以使用独木舟 $1$ 或者 $2$。注意，她不能连续使用独木舟 $0$ 两次。在两种情况下，Bu Dengklek 都回到了岛屿 $0$ 上。然而，有独木舟没停靠在旅行开始前它们所在的岛屿，而 Bu Dengklek 此后却无法再使用任何独木舟，因为唯一停靠在岛屿 $0$ 的独木舟是她刚用过的那艘。由于不存在合理旅程，该函数应当返回 false。

约束条件

• $2 \le N \le 10^5$；
• $1 \le M \le 2 \times 10^5$；
• $0 \le U_i \le N - 1$ 且 $0 \le V_i \le N - 1$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）；
• $U_i \neq V_i$（对于所有满足 $0 \le i \le M - 1$ 的 $i$）。

子任务

1. （5 分）$N = 2$。
2. （5 分） $N \le 400$。 对于每一对不同的岛屿 $x$ 和 $y$（$0 \le x \lt y \le N - 1$），恰好有两艘可在它们之间航行的独木舟。 其中一艘停靠在岛屿 $x$，而另一艘停靠在岛屿 $y$。
3. （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}$。
4. （24 分） $N \le 1000$，$M$ 是偶数，而且对于满足 $0 \le i \le M - 1$ 的所有偶数 $i$，独木舟 $i$ 和 $i + 1$ 都可以用于在岛屿 $U_i$ 和 $V_i$ 之间航行。两艘独木舟最初都停靠在岛屿 $U_i$ 处。 形式化地，$U_i = U_{i + 1}$ 且 $V_i = V_{i + 1}$。
5. （45 分）没有额外的约束条件。

对于每个存在合理旅程的测试用例，你的解答：

• 如果返回一个合理旅程，将得到全部分数，
• 如果返回 true，或返回一个超过 $2\;000\;000$ 个整数的数组，或返回一个未给出合理旅程的数组，将得到 $35\%$ 的分数，
• 在其他情况下得分为 $0$。

对于每个不存在合理旅程的测试用例，你的解答：

• 如果返回 false，将得到全部分数，
• 在其他情况下得分为 $0$。

注意，每个子任务上的最终得分，为该子任务中所有测试用例上的最低得分。

评测程序示例

评测程序示例读取如下格式的输入：

• 第 $1$ 行：$N \; M$；
• 第 $2 + i$ 行（$0 \le i \le M - 1$）：$U_i \; V_i$。

测试程序示例将按照如下格式打印你的答案：

• 如果 find_journey 返回一个 bool：
  • 第 $1$ 行：$0$；
  • 第 $2$ 行：如果 find_journey 返回 false 则为 $0$，否则为 $1$。
• 如果 find_journey 返回一个 int[]，该数组中的元素记为 $c[0], c[1], \ldots c[k-1]$。测试程序示例打印出：
  • 第 $1$ 行：$1$；
  • 第 $2$ 行：$k$；
  • 第 $3$ 行：$c[0] \; c[1] \; \ldots \; c[k-1]$。

约定

题面在给出函数接口时，会使用一般性的类型名称 void、bool、int、int[]（数组）和 union(bool, int[])。

在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：

void	bool	int	int[]
void	bool	int	std::vector<int>

union(bool, int[])	数组 a 的长度
std::variant<bool, std::vector<int>>	a.size()

C++ 语言里，std::variant 定义在 <variant> 头文件中。 一个返回类型为 std::variant<bool, std::vector<int>> 的函数可以返回一个 bool 或一个 std::vector<int>。 以下示例代码给出了三个返回 std::variant 的函数，它们都能正常工作：

std::variant<bool, std::vector<int>> foo(int N) {
    return N % 2 == 0;
}

std::variant<bool, std::vector<int>> goo(int N) {
    return std::vector<int>(N, 0);
}

std::variant<bool, std::vector<int>> hoo(int N) {
    if (N % 2 == 0) {
        return false;
    }

    return std::vector<int>(N, 0);
}