题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Trzy Wieże

Bajtocy 刚刚荣升为 Bajtocja 的首席建筑师。Bajtocja 由 $n$ ($1 \leq n \leq 200000$) 座城市组成，通过 $m$ ($1 \leq m \leq 300000$) 条双向道路连接，每条道路有唯一的正整数维护成本。城市编号从 $0$ 到 $n-1$，道路编号从 $0$ 到 $m-1$。道路网络保证任意两城可达，维护成本互不相同，每对城市最多由一条道路连接，且无道路连接同一城市。

新官上任的 Bajtocy 面临一项艰巨任务：国王 Bajtazar 要求关闭部分道路，同时确保任意两城仍可连通，以最小化剩余道路的维护成本总和。Bajtocy 需要确定哪些道路应保留。

然而，Bajtocy 并不知道各道路的具体维护成本，只能通过向顾问询问获取信息。询问分为两类：

• 独立型：比较两条无公共端点的道路成本。
• 星型：在一组共享同一端点的道路中，找出成本最低的道路。

你的任务是帮助 Bajtocy 使用这两种询问方式，确定应保留的道路集合。评分将根据两种询问的使用次数确定。

---

交互方式

本题为交互题，需编写程序通过询问确定结果。你可以选择使用提供的库或标准输入输出进行交互，但不可同时使用两者。选手文件提供两种交互方式的示例实现。程序不可打开任何文件，可使用标准错误输出（stderr），但需注意时间消耗。标准输出的冗余数据可能导致「Wrong Answer」。禁止故意干扰评测库的内部运行。

注意：内存和时间限制仅针对你的程序，不包括交互器。

---

方式 1：使用库交互

在此方式下，程序不可使用标准输入输出。

C++

程序开头需包含：

#include "redlib.h"

库提供以下函数：

• int DajN()：返回城市数量 $n$。
• std::vector<std::pair<int,int>> DajDrogi()：返回 $m$ 个道路描述，每条道路为一个数对 $(x, y)$ ($0 \leq x, y < n$, $x \neq y$)，表示连接城市 $x$ 和 $y$。道路按返回顺序编号，成本互不相同。
• int Niezalezne(int a, int b)：比较无公共端点的道路 $a$ 和 $b$ ($0 \leq a, b < m$)，若 $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：返回城市数量 $n$。
• DajDrogi() -> list[tuple[int, int]]：返回 $m$ 个道路描述，每条道路为元组 $(x, y)$ ($0 \leq x, y < n$, $x \neq y$)，表示连接城市 $x$ 和 $y$。道路按返回顺序编号，成本互不相同。
• Niezalezne(a: int, b: int) -> int：比较无公共端点的道路 $a$ 和 $b$ ($0 \leq a, b < m$)，若 $a$ 成本较低返回 $-1$，若 $b$ 成本较低返回 $1$。
• Gwiazda(t: list[int]) -> int：比较共享同一端点的道路集合 $t$，返回成本最低的道路编号。
• Wynik(t: list[int])：提交保留道路的编号集合，满足任务要求。调用后程序应终止。

---

方式 2：标准输入输出交互

• 第一行从标准输入读取两个整数 $n$, $m$，分别表示城市数和道路数。
• 接下来的 $m$ 行，每行包含两个整数 $x$, $y$ ($0 \leq x, y < n$, $x \neq y$)，描述一条道路，连接城市 $x$ 和 $y$，按输入顺序编号，成本互不相同。

独立型询问

输出一行，包含三个整数 $1$, $a$, $b$ ($0 \leq a, b < m$)，比较无公共端点的道路 $a$ 和 $b$。
随后读取一个整数：$-1$ 表示 $a$ 成本较低，$1$ 表示 $b$ 成本较低。

星型询问

输出一行，包含 $2$, $k$ 和 $k$ 个道路编号，比较共享同一端点的 $k$ 条道路。
随后读取一个整数，表示成本最低的道路编号。

提交结果

输出一行，包含 $3$, $k$ 和 $k$ 个道路编号，表示保留的道路集合，满足任务要求。

---

注意事项

以下情况将导致「Wrong Answer」：

• 使用无效道路编号（不在 $\{0, 1, \ldots, m-1\}$ 内）。
• 用 Niezalezne 比较有公共端点的道路（包括同一道路）。
• 用 Gwiazda 比较无公共端点的道路集合或空集合。
• 用 Wynik 提交包含重复道路编号的集合。

---

样例

假设 $n=4$, $m=4$，道路连接城市对 $(0, 3), (0, 2), (1, 2), (2, 3)$，维护成本分别为 $3, 1, 2, 4$。交互过程可能如下：

调用	结果	说明
DajN	$4$	获取城市数量 $n=4$
DajDrogi	$\{(0,3), (0,2), (1,2), (2,3)\}$	获取 $m=4$ 条道路列表
Gwiazda([3, 1, 2])	$1$	道路 $1$ 在集合中成本最低
Niezalezne(0, 2)		道路 $0$ 成本高于道路 $2$
Gwiazda([3, 0])	$0$	道路 $0$ 成本低于道路 $3$
Niezalezne(2, 0)	$-1$	道路 $2$ 成本低于道路 $0$
Wynik([0, 2, 1])	—	正确提交保留道路集合

---

附加样例

1. $n=200$, $m=199$，无法移除任何道路。
2. $n=1500$, $m=2998$，除一个城市外，其余城市形成环，剩余城市与环上每城相连。
3. $n=200000$, $m=300000$，道路 $i$ ($0 \leq i < n$) 连接城市 $i$ 和 $(i+1) \bmod n$，道路 $n+i$ ($0 \leq i < m-n$) 连接城市 $i$ 和 $(i+5) \bmod n$，成本为 $i+1$。

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$n \leq 200$, $m \leq 300$	$18$
2	$n \leq 2000$, $m \leq 3000$	$33$
3	$m = n$	$12$
4	$m \leq n + 10$	$16$
5	无附加限制	$21$

单次测试得分基于独立型询问次数 $p$ 和星型询问次数 $q$，如下表所示：

$p \backslash q$	$0 \leq q \leq n-1$	$n-1 < q \leq 2 \cdot (n-1)$	$2 \cdot (n-1) < q$
$0 \leq p \leq 15 \cdot m$	$100\%$	$75\%$	$40\%$
$15 \cdot m < p \leq \max(15, n) \cdot m$	$50\%$	$30\%$	$20\%$
$p > \max(15, n) \cdot m$	$15\%$	$10\%$	$5\%$

若答案错误或发生其他错误（运行错误、超时等），测试点得分为 $0$。