CF566B Replicating Processes

一家大型软件公司开发了自己的社交网络。分析师们发现，在假期、重大体育赛事以及其它重要活动期间，用户会更频繁地登录网络，从而导致基础设施的负载大幅增加。 在这个任务中，我们假设社交网络运行在 $n$ 台服务器上，共有 $4n$ 个进程。所有服务器的配置完全相同，每台服务器具有 $1$ GB = $1024$ MB 的内存 $^{(1)}$。每个进程占用服务器 $100$ MB 内存。同时，为了维持服务器的正常运行，还需要额外占用大约 $100$ MB 内存。因此，每台服务器最多只能同时运行 $9$ 个社交网络进程。 当前，每台服务器正好运行着 $4$ 个进程。然而，在负载高峰时，有时需要将现有的 $4n$ 个进程通过复制替换为 $8n$ 个新进程。更正式地说，有一组复制规则，第 $i$ 条规则（$1 \leq i \leq 4n$）记作 $a_i \to (b_i, c_i)$，其中 $a_i$、$b_i$、$c_i$（$1 \leq a_i, b_i, c_i \leq n$）都是服务器编号。这表示需要将运行在服务器 $a_i$ 上的一个旧进程销毁，并在服务器 $b_i$ 和 $c_i$ 上分别新建两个相同的进程。两个新复制的进程可以在同一台服务器上（即允许 $b_i = c_i$），也可以在原服务器上生成（即 $a_i$ 可以等于 $b_i$ 或 $c_i$）。在执行规则 $a_i \to (b_i, c_i)$ 时，首先销毁 $a_i$ 服务器上的进程，然后依次在 $b_i$ 和 $c_i$ 服务器上产生新进程。 共有 $4n$ 条这样的规则，它们会销毁原有的 $n$ 台服务器上的 $4n$ 个进程，并在操作完成后生成 $8n$ 个复制进程。此时每台服务器都有恰好 $8$ 个进程。然而，规则只能逐条依次执行，因此服务器的内存限制会约束规则的执行顺序。 请根据这组规则，确定一种执行 $4n$ 条规则的顺序，使得在任意时刻，每台服务器上的进程总数（包括旧进程和新进程）最多不超过 $9$ 个。若不存在这样的执行顺序，请输出“不可能”。

第一行包含整数 $n$（$1 \leq n \leq 30000$），表示社交网络的服务器数量。 接下来的 $4n$ 行给出进程复制的规则，第 $i$ 行（$1 \leq i \leq 4n$）包含 $a_i, b_i, c_i$（$1 \leq a_i, b_i, c_i \leq n$），描述了规则 $a_i \to (b_i, c_i)$。 保证所有 $a_i$ 中每个服务器编号 $1$ 到 $n$ 恰好出现 $4$ 次，而在所有 $b_i$ 和 $c_i$ 的集合中，每个服务器编号恰好出现 $8$ 次。

如果不存在满足要求的执行顺序，输出一行“NO”。 否则，输出第一行“YES”，第二行输出 $4n$ 个 $1$ 到 $4n$ 的数，表示规则的执行顺序。该序列应为 $1$ 到 $4n$ 的一个排列，序号之间用空格隔开。 若存在多种答案，输出其中任意一种均可。

$^{(1)}$ 为了严谨地描述，服务器的内存大小为 $1$ GiB = $1024$ MiB，进程需要 $100$ MiB 内存。注意 $1$ Gibibyte (GiB) 等于 $2^{30}$ 字节，$1$ Mebibyte (MiB) 等于 $2^{20}$ 字节。 在第一个样例测试中，网络使用了两台服务器，每台服务器初始都有 $4$ 个进程。按照复制规则，每个进程需要销毁并在其它服务器上复制两次。题目中给出了一种可行答案：执行规则 $1$ 和 $2$ 后，第一台服务器还剩 $2$ 个旧进程，第二台有 $8$ 个进程（$4$ 个旧进程和 $4$ 个新进程）；再执行规则 $5$ 和 $6$，两台服务器均有 $6$ 个进程（$2$ 个旧进程和 $4$ 个新进程）；然后执行规则 $3$ 和 $7$，两台服务器各有 $7$ 个进程（$1$ 个旧进程和 $6$ 个新进程）；最后执行规则 $4$ 和 $8$，两台服务器均有 $8$ 个进程。任意时刻，单台服务器上的进程数均没有超过 $9$。 在第二个样例测试中，网络使用了三台服务器。各台服务器上的三个进程都在本机复制成两个新进程，第四个则分别在另外两台服务器上各产生一个新进程。经过执行规则 $2,3,4,6,7,8,10,11,12$ 后，每台服务器有 $7$ 个进程（$6$ 个旧进程和 $1$ 个新进程），最后执行规则 $1,5,9$，各服务器均有 $8$ 个进程。过程中，任意时刻单台服务器上的进程数均没有超过 $9$。 由 ChatGPT 5 翻译