P17519 [ECUSTPC 2026 Fall] 星之彼端

> *今夜天空深远宁静，我们望的是同一颗星星吗？* **这是一道通信题，请注意本题不同寻常的数据范围约束。**

那是整个 ECUST 都早已遗忘的久远过去…… 在那个无人记得的年代，竹林和千外并肩战斗，共同生活，一起仰望同一片星空。后来，语言被风沙掩埋，道路被海洋截断，连名字都从史书里褪色。唯一没有被带走的，是头顶那片沉默而辽阔的星图。它公开、闪耀、亘古不变，却没有人知道其中哪几颗星曾被他们悄悄连成一句话。 本题共有 $20$ 个测试点。 给定一个无向图 $G = (V, E)$，其中 $|V| = 2000$, $|E| = 43\,600$。图 $G$ 不包含重边和自环，并且保证由以下方式生成：初始时，图 $G$ 包含 $|V|$ 个点且没有任何边。随后，生成器将重复执行以下操作 $|E|$ 次：在当前所有尚未被边连接的点对中，等概率地随机选取一对点，并在它们之间添加一条无向边。 你的程序将被运行两次： **第一次运行** 在第一次运行时，你将扮演竹林。你需要在图 $G$ 中选择 $n$ 个诱导四元环并输出。这些诱导四元环可以拥有共同的顶点。 - **诱导四元环的定义：** 选定图 $G$ 中的 $4$ 个点，这 $4$ 个点之间**恰好**存在 $4$ 条边，且构成一个简单的环（即内部不能有对角线相连）。 **第二次运行** 在第二次运行时，你将扮演千外。评测机将获取你在第一次运行中输出的所有四元环。你需要回答 $q$ 次询问。对于每一个询问，评测机会挑选一个四元环，任选其中一个点并删除，然后输出剩余三个点的编号。你需要回答这三个点来自于竹林输出的第几个四元环。 这三个点可能同时来自于你挑选的多个多元环，但你必须回答评测机挑选的那一个。

**第一次运行** 第一行包含一个字符串 `send`。 第二行包含一个整数 $n$（$n = 200\,000$），表示需要输出的诱导四元环数量。 第三行包含两个整数 $|V|$ 和 $|E|$。 接下来 $|E|$ 行，每行包含两个整数 $u, v$，表示顶点 $u$ 和 $v$ 之间有一条无向边 ($1 \le u, v \le |V|$)。 **第二次运行** 第一行包含一个字符串 `receive`。 第二行包含两个整数 $|V|$ 和 $|E|$。 接下来 $|E|$ 行，每行包含两个整数 $u, v$，表示顶点 $u$ 和 $v$ 之间有一条无向边 ($1 \le u, v \le |V|$)。 第 $|E| + 3$ 行包含一个整数 $q$ ($q = 4n$)，表示接收到的顶点集合数量。 接下来的 $q$ 行，每行包含 $3$ 个整数，代表评测机从你第一次运行输出的某个四元环中删除一个顶点后得到的顶点集合。

**第一次运行** 输出 $n$ 行。第 $i$ 行输出 $4$ 个整数 $v_1, v_2, v_3, v_4$，代表第 $i$ 个诱导四元环的四个顶点编号。 **第二次运行** 输出 $q$ 行。对于每一组接收到的顶点集合，输出一个整数 $i$ ($1 \le i \le n$)，表示该集合属于第 $i$ 个四元环。

### 样例 1 解释 由于完整数据过大，题面省略了样例的部分内容。你可以在附件中查看第一次运行的完整输入。