← 返回题目列表

Codeforces · 566/B

B. 复制进程

中文机器翻译题面 查看原题

一家大型软件公司开发自己的社交网络。分析人士发现,节假日期间,大型体育赛事等重大赛事用户开始更频繁地进入网络,导致基础设施负载大幅增加。

作为此任务的一部分,我们假设社交网络是在 n 个服务器上运行的 4n 个进程。所有服务器都是完全相同的机器,每台机器的 RAM 容量为 1 GB = 1024 MB (1)。每个进程占用服务器上 100 MB 的 RAM。同时,维持服务器的生存能力还需要大约 100 MB 的 RAM。因此,每个服务器最多可以有9个不同的社交网络进程。

现在,n 个服务器中的每一个都运行着 4 个进程。然而,在峰值负载时,有时需要通过创建 8n 个新进程而不是旧进程来复制现有的 4n 个进程。更正式地说,有一组复制规则,其中第 i 个(1 ≤ i ≤ 4n)的复制规则的形式为 ai → (bi, ci),其中 ai、bi 和 ci (1 ≤ ai, bi, ci ≤ n) 是服务器的数量。这意味着,服务器 bi 和 ci 上运行的进程的两个新副本应该出现在服务器 ai 上,而不是运行在服务器 ai 上的旧进程。两个新的复制进程可以位于同一服务器上(即 bi 可能等于 ci),甚至可以位于原始进程所在的同一服务器上(即 ai 可能等于 bi 或 ci)。在规则ai→(bi,ci)的执行过程中,首先服务器ai上的进程被销毁,然后服务器bi上出现一个进程,然后服务器ci上出现一个进程。

有一组 4n 规则,销毁来自 n 个服务器的所有原始 4n 个进程,并在其应用后创建 8n 个复制进程,此外,n 个服务器中的每一个上都将恰好有 8 个进程。然而,规则只能连续应用,因此服务器的RAM量对规则的应用过程施加了限制。

根据这组规则确定要应用所有4n规则的顺序,以便在任何给定时间每个服务器的内存最多包含9个进程(新旧一起),否则告诉这是不可能的。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 30 000) — 社交网络的服务器数量。

接下来的 4n 行包含复制过程的规则,这些行中的第 i (1 ≤ i ≤ 4n) 行形式为 ai, bi, ci (1 ≤ ai, bi, ci ≤ n) 并描述规则 ai → (bi, ci)。

保证服务器从 1 到 n 的每个数字在所有 ai 的集合中出现四次,在所有 bi 和 ci 联合的集合中出现八次。

输出

如果执行规则所需的顺序不存在,则打印“NO”(不带引号)。

否则,在第一行中打印“YES”(不带引号),并在第二行中打印从 1 到 4n 的 4n 个数字序列,按照规则的应用顺序给出规则的编号。该序列应该是一个排列,即从 1 到 4n 的每个数字只包含一次。

如果有多种可能的变体,您可以打印其中任何一个。

示例

输入 #1

2
1 2 2
1 2 2
1 2 2
1 2 2
2 1 1
2 1 1
2 1 1
2 1 1

输出 #1

YES
1 2 5 6 3 7 4 8

输入 #2

3
1 2 3
1 1 1
1 1 1
1 1 1
2 1 3
2 2 2
2 2 2
2 2 2
3 1 2
3 3 3
3 3 3
3 3 3

输出 #2

YES
2 3 4 6 7 8 10 11 12 1 5 9

注意

(1) 为了非常准确,我们应该注意到服务器内存量为 1 GiB = 1024 MiB,进程需要 100 MiB RAM,其中 1 GiB (GiB) 是 230 字节的 RAM 量,1 Mebibyte (MiB) 是 220 字节的 RAM 量。

在第一个示例测试中,网络使用两台服务器,每台服务器最初都有四个启动的进程。根据复制规则,每个进程都必须被销毁并在另一台服务器上运行两次。语句中给出了一个可能的答案:应用规则 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 个。