CF566B.Replicating Processes

A Large Software Company develops its own social network. Analysts have found that during the holidays, major sporting events and other significant events users begin to enter the network more frequently, resulting in great load increase on the infrastructure.

As part of this task, we assume that the social network is 4_n_ processes running on the n servers. All servers are absolutely identical machines, each of which has a volume of RAM of 1 GB = 1024 MB (1). Each process takes 100 MB of RAM on the server. At the same time, the needs of maintaining the viability of the server takes about 100 more megabytes of RAM. Thus, each server may have up to 9 different processes of social network.

Now each of the n servers is running exactly 4 processes. However, at the moment of peak load it is sometimes necessary to replicate the existing 4_n_ processes by creating 8_n_ new processes instead of the old ones. More formally, there is a set of replication rules, the i-th (1 ≤ i ≤ 4_n_) of which has the form of a__i → (b__i, c__i), where a__i, b__i and c__i (1 ≤ a__i, b__i, c__i ≤ n) are the numbers of servers. This means that instead of an old process running on server a__i, there should appear two new copies of the process running on servers b__i and c__i. The two new replicated processes can be on the same server (i.e., b__i may be equal to c__i) or even on the same server where the original process was (i.e. a__i may be equal to b__i or c__i). During the implementation of the rule a__i → (b__i, c__i) first the process from the server a__i is destroyed, then appears a process on the server b__i, then appears a process on the server c__i.

There is a set of 4_n_ rules, destroying all the original 4_n_ processes from n servers, and creating after their application 8_n_ replicated processes, besides, on each of the n servers will be exactly 8 processes. However, the rules can only be applied consecutively, and therefore the amount of RAM of the servers imposes limitations on the procedure for the application of the rules.

According to this set of rules determine the order in which you want to apply all the 4_n_ rules so that at any given time the memory of each of the servers contained at most 9 processes (old and new together), or tell that it is impossible.

一家大型软件公司开发了自己的社交网络。分析人员发现，在节假日期间、重大体育赛事及其他重要事件期间，用户会更频繁地登录该网络，从而导致基础设施负载大幅增加。

在本题中，我们假设该社交网络由 $4n$ 个进程组成，运行在 $n$ 台服务器上。所有服务器均为完全相同的机器，每台服务器的内存容量为 $1\ \text{GB} = 1024\ \text{MB}$（1）。每个进程在服务器上占用 $100\ \text{MB}$ 内存。此外，维持服务器正常运行还需额外约 $100\ \text{MB}$ 内存。因此，每台服务器最多可承载 $9$ 个社交网络进程。

目前，每台 $n$ 台服务器上恰好运行着 $4$ 个进程。然而，在峰值负载时刻，有时需通过创建 $8n$ 个新进程来替代原有的 $4n$ 个进程，即对原有进程进行复制。更形式化地说，存在一组复制规则，其中第 $i$ 条规则（$1 \le i \le 4n$）形如 $a_i \to (b_i,\,c_i)$，其中 $a_i$、$b_i$ 和 $c_i$（$1 \le a_i,\,b_i,\,c_i \le 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$ 个复制进程；且最终每台 $n$ 台服务器上恰好运行 $8$ 个进程。然而，这些规则只能依次逐条应用，因此各服务器的内存容量对规则的应用顺序构成了限制。

请根据给定的这组规则，确定一种应用全部 $4n$ 条规则的顺序，使得在任意时刻，每台服务器的内存中所容纳的进程总数（包括尚未销毁的旧进程和已生成的新进程）均不超过 $9$ 个；若不存在这样的顺序，则判定为不可能。

The first line of the input contains integer n (1 ≤ n ≤ 30 000) — the number of servers of the social network.

Next 4_n_ lines contain the rules of replicating processes, the i-th (1 ≤ i ≤ 4_n_) of these lines as form a__i, b__i, c__i (1 ≤ a__i, b__i, c__i ≤ n) and describes rule a__i → (b__i, c__i).

It is guaranteed that each number of a server from 1 to n occurs four times in the set of all a__i, and eight times among a set that unites all b__i and c__i.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 30\,000$），表示社交网络中服务器的数量。

接下来的 $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$ 的每个服务器编号恰好出现四次；而在所有 $b_i$ 与 $c_i$ 合并构成的集合中，每个服务器编号恰好出现八次。

If the required order of performing rules does not exist, print "NO" (without the quotes).

Otherwise, print in the first line "YES" (without the quotes), and in the second line — a sequence of 4_n_ numbers from 1 to 4_n_, giving the numbers of the rules in the order they are applied. The sequence should be a permutation, that is, include each number from 1 to 4_n_ exactly once.

If there are multiple possible variants, you are allowed to print any of them.

如果不存在满足要求的规则执行顺序，则输出 "NO"（不带引号）。

否则，在第一行输出 "YES"（不带引号），在第二行输出一个由 $1$ 到 $4n$ 的 $4n$ 个数字组成的序列，表示规则按执行顺序所对应的编号。该序列为一个排列，即恰好包含从 $1$ 到 $4n$ 的每个数字一次。

若存在多种可能的方案，输出任意一种即可。

(1) To be extremely accurate, we should note that the amount of server memory is 1 GiB = 1024 MiB and processes require 100 MiB RAM where a gibibyte (GiB) is the amount of RAM of 230 bytes and a mebibyte (MiB) is the amount of RAM of 220 bytes.

In the first sample test the network uses two servers, each of which initially has four launched processes. In accordance with the rules of replication, each of the processes must be destroyed and twice run on another server. One of the possible answers is given in the statement: after applying rules 1 and 2 the first server will have 2 old running processes, and the second server will have 8 (4 old and 4 new) processes. After we apply rules 5 and 6, both servers will have 6 running processes (2 old and 4 new). After we apply rules 3 and 7, both servers will have 7 running processes (1 old and 6 new), and after we apply rules 4 and 8, each server will have 8 running processes. At no time the number of processes on a single server exceeds 9.

In the second sample test the network uses three servers. On each server, three processes are replicated into two processes on the same server, and the fourth one is replicated in one process for each of the two remaining servers. As a result of applying rules 2, 3, 4, 6, 7, 8, 10, 11, 12 each server would have 7 processes (6 old and 1 new), as a result of applying rules 1, 5, 9 each server will have 8 processes. At no time the number of processes on a single server exceeds 9.

（1）为了极度精确，我们需注意：服务器内存容量为 1 GiB = 1024 MiB，而每个进程需占用 100 MiB 内存；其中，gibibyte（GiB） 表示 $2^{30}$ 字节的内存容量，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。