注意事项

由于 IO 效率等问题，在 LibreOJ 上暂不支持标准输入输出交互。

题目描述

题目译自 XXXII Olimpiada Informatyczna – III etap Redukcja połączeń

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 并不知道各道路的具体维护成本，只能通过向顾问询问获取信息。询问分为两类：

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

你的任务是帮助 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])：提交保留道路的编号集合，满足任务要求。调用后程序应终止。

注意事项

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

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

方式 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」：

• 使用无效道路编号。
• 独立型询问比较有公共端点的道路。
• 星型询问使用无公共端点的道路集合或空集合。
• 提交结果包含重复道路编号。

C++（流式输入输出）

包含头文件 <iostream>，输出每行使用 std::endl。单组提问示例：

std::cout << 1 << " " << a << " " << b << std::endl;
std::cin >> wynik;

C++（stdio 输入输出）

包含头文件 <cstdio>，输出每行调用 fflush(stdout)。单组提问示例：

printf("1 %d %d\n", a, b);
fflush(stdout);
scanf("%d", &wynik);

Python

输出每行设置 flush=True。单组提问示例：

print(f"1 {a} {b}", flush=True)
wynik = int(input())

示例评测程序

「文件」中提供了 C++ 和 Python 的示例（错误）解决方案，展示两种交互方式，以及样例（red0.in, red[1-3]ocen.in）、交互库和示例评测程序。测试用例格式为：

• 第一行：整数 $n, m$。
• 接下来的 $m$ 行：三个整数 $x_i, y_i, w_i$，表示第 $i$ 条道路连接城市 $x_i$ 和 $y_i$，成本为 $w_i$。

方式 1：使用库交互

red.cpp 和 red.py 为基于库交互的示例（错误）解决方案。C++ 编译命令：

g++ -O3 -static -std=c++20 redlib.cpp red.cpp -o red.e

运行示例测试：

# C++
./red.e < red0.in
# Python
python3 red.py < red0.in

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

red2.cpp 和 red2.py 为基于标准输入输出的示例（错误）解决方案。C++ 使用 make 编译，生成 red2.e。运行使用 run.sh 脚本：

# C++
./run.sh "./red2.e" red0.in
# Python
./run.sh "python3 red2.py" red0.in

示例评测程序与正式评测使用的评测程序不同，可能不验证输入或函数参数的合法性。提交评测的代码将在样例上使用正式评测程序。

样例

假设 $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)	$1$	道路 $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$。