Bajtocy 刚刚被任命为 Bajtocja 的首席架构师。Bajtocja 由 $n$ ($1 \le n \le 200\,000$) 个城市组成，这些城市由 $m$ ($1 \le m \le 300\,000$) 条双向道路连接，每条道路都有一个正整数维护成本。城市和道路分别从 $0$ 到 $n-1$ 和 $0$ 到 $m-1$ 编号。已知道路网络允许在任意两个城市之间通行，且所有道路的维护成本各不相同。每对城市之间最多只有一条道路相连。没有道路连接城市与其自身。

随着职位的晋升，Bajtocy 面临着一项艰巨的任务：Bajtazar 国王希望关闭一些道路，同时确保仍然可以在任意两个城市之间通行。显然，他希望最小化未关闭道路的维护成本之和。Bajtocy 被要求确定应该保留哪些道路。

遗憾的是，Bajtocy 不知道每条道路的维护成本。但他可以向顾问提问。每个问题属于以下两种类型之一： 独立查询：比较两条没有公共端点的道路的成本。 星形查询：确定给定一组具有公共端点的道路中，哪一条道路的成本最低。

请帮助 Bajtocy 确定应该保留哪些道路，仅使用这两种类型的查询。你的解决方案获得的得分将取决于每种类型查询的数量——请参阅“评分”部分。

交互

本题为交互题。与评测程序的通信可以通过库或标准输入输出进行。你可以选择其中一种方式，但不能同时使用两种方法。

你的程序不得打开任何文件。程序可以使用标准诊断输出（stderr），但请注意这会消耗时间。任何输出到标准输出的冗余数据都可能被视为错误答案。严禁故意干扰评测库的内部运行。

注意：给出的内存和时间限制仅适用于你的解决方案（不包括评测程序）。

选项 1：使用库进行通信

在此选项中，你的程序不能使用标准输入和输出。

C++ 程序开头必须包含： #include "redlib.h"

库提供以下函数： int DajN()：返回 Bajtocja 的城市数量 $n$。 std::vector<std::pair<int,int> > DajDrogi()：返回 $m$ 对描述 Bajtocja 道路的数字。每对由两个整数 $x$ 和 $y$ ($0 \le x, y < n, x \neq y$) 组成，表示由道路连接的城市。道路按此函数返回的顺序编号。请记住，道路的维护成本各不相同。 int Niezalezne(int a, int b)：比较编号为 $a$ 和 $b$ ($0 \le a, b < n$) 且没有公共端点的道路；如果道路 $a$ 更便宜，则返回 $-1$；如果道路 $b$ 更便宜，则返回 $1$。 int Gwiazda(std::vector<int> t)：比较一组具有公共端点的道路；向量 $t$ 应包含道路编号，结果是该集合中成本最低的道路编号。 * void Wynik(std::vector<int> t)：接收满足题目条件的道路编号集合。执行此函数后，程序必须终止。

Python 程序开头必须包含： from redlib import DajN, DajDrogi, Niezalezne, Gwiazda, Wynik

库提供以下函数： DajN() -> int：返回 Bajtocja 的城市数量 $n$。 DajDrogi() -> list[tuple[int, int]]：返回 $m$ 对描述 Bajtocja 道路的数字。每对由两个整数 $x$ 和 $y$ ($0 \le x, y < n, x \neq y$) 组成，表示由道路连接的城市。道路按此函数返回的顺序编号。请记住，道路的维护成本各不相同。 Niezalezne(a : int, b : int) -> int：比较编号为 $a$ 和 $b$ ($0 \le a, b < n$) 且没有公共端点的道路；如果道路 $a$ 更便宜，则返回 $-1$；如果道路 $b$ 更便宜，则返回 $1$。 Gwiazda(t : list[int]) -> int：比较一组具有公共端点的道路；列表 $t$ 应包含道路编号，结果是该集合中成本最低的道路编号。 * Wynik(t : list[int])：接收满足题目条件的道路编号集合。执行此函数后，程序必须终止。

一般说明 使用任何带有无效参数的函数都将导致“错误答案”判决。无效参数包括： 提供集合 $\{0, 1, \dots, m-1\}$ 之外的道路编号。 使用 Niezalezne 函数比较具有公共端点的道路（包括道路与自身比较）。 使用没有公共端点的道路集合调用 Gwiazda 函数。 使用空道路集合调用 Gwiazda 函数。 * 使用包含重复道路的集合调用 Wynik 函数。

选项 2：通过标准输入/输出进行通信

在标准输入的第一行，将有两个整数 $n$ 和 $m$，表示 Bajtocja 的城市数量和道路数量。接下来输入 $m$ 行，描述 Bajtocja 的道路。每行包含两个整数 $x$ 和 $y$ ($0 \le x, y < n, x \neq y$)，表示由道路连接的城市。道路按输入顺序编号。请记住，道路的维护成本各不相同。

要进行独立查询，请输出一行，依次包含数字 $1$ 和两个整数 $a$ 和 $b$ ($0 \le a, b < n$)。此查询比较编号为 $a$ 和 $b$ 且没有公共端点的道路。然后从标准输入读取一个整数；如果道路 $a$ 更便宜，则该值为 $-1$；如果道路 $b$ 更便宜，则该值为 $1$。

要进行星形查询，请输出一行，依次包含数字 $2$、道路数量 $k$ 以及 $k$ 个道路编号。此查询比较给定编号的 $k$ 条道路。然后从标准输入读取一个整数；该值为给定道路中成本最低的道路编号。

最后，输出一行，依次包含数字 $3$、道路数量 $k$ 以及 $k$ 个道路编号。这应该是满足题目条件的道路编号集合。

使用任何无效参数进行查询都将导致“错误答案”判决。无效参数包括： 提供集合 $\{0, 1, \dots, m-1\}$ 之外的道路编号。 使用独立查询比较具有公共端点的道路。 进行没有公共端点的道路集合的星形查询。 进行空道路集合的星形查询。 * 提供包含重复道路的集合作为答案。

C++，流式输入/输出 必须包含 <iostream> 头文件。在输出每一行后，请使用 std::endl。

C++，stdio 输入/输出 必须包含 <cstdio> 头文件。在输出每一行后，请使用 fflush(stdout)。

Python 在输出每一行后，请使用 flush = True。

样例

输入格式 1

4 4
0 3
0 2
1 2
2 3

输出格式 1

1 0 2
1
2 3 3 1 2
1
2 2 3 0
0
2 2 2 0
-1
3 3 0 2 1

说明

假设 $n=4, m=4$，道路连接 $(0, 3), (0, 2), (1, 2), (2, 3)$，成本分别为 $3, 1, 2, 4$。

评分

测试集分为以下子任务。对于每个子任务，程序将在一定数量的测试用例上运行。子任务的最终得分是该子任务所有测试用例得分的最小值。

单个测试用例的得分计算如下：设 $p$ 为独立查询的数量，$q$ 为星形查询的数量。你的程序得分由下表给出：

请注意，如果程序超过了给定测试用例时间限制的一半，得分将相应缩减。否则，如果答案错误或发生任何其他错误（运行时错误、超时等），该测试用例的得分为 0。