B. Репликация процессов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Большая Софтверная Компания разрабатывает свою собственную социальную сеть. Аналитики компании обнаружили, что в дни праздников, крупных спортивных мероприятий и прочих значимых событий пользователи начинают заходить в сеть гораздо чаще, в результате чего сильно возрастает нагрузка на инфраструктуру.

В рамках данной задачи будем считать, что социальная сеть представляет собой 4n процессов, запущенных на n серверах. Все сервера представляют собой абсолютно идентичные машины, каждая из которых располагает объёмом оперативной памяти в 1 ГБ = 1024 МБ (1). Каждый из процессов занимает на сервере 100 мегабайт оперативной памяти. При этом, на нужды поддержания жизнеспособности сервера уходит ещё около 100 мегабайт оперативной памяти. Таким образом, на каждом сервере может быть запущено до 9 различных процессов социальной сети.

Сейчас на каждом из n серверов запущено ровно 4 процесса. Однако в момент пиковой нагрузки иногда бывает нужно реплицировать имеющиеся 4n процессов, создав 8n новых процессов вместо старых. Более формально, имеется набор правил репликации, i-е (1 ≤ i ≤ 4n) из которых имеет вид ai → (bi, ci), где ai, bi и ci (1 ≤ ai, bi, ci ≤ n) — номера серверов. Такое правило означает, что вместо одного старого процесса, работающего на сервере ai, должно возникнуть две новые копии процесса, работающих на серверах bi и ci. При этом, два новых реплицированных процесса могут оказаться на одном и том же сервере (то есть, bi может быть равно ci) или даже на том же самом сервере, с которого был исходный процесс (то есть ai может быть равно bi или ci). В ходе выполнения правила ai → (bi, ci) сначала уничтожается процесс с сервера ai, затем возникает процесс на сервере bi, а затем — процесс на сервере ci.

Имеется набор из 4n правил, уничтожающих все исходные 4n процессов с n серверов, и создающие после их применения 8n реплицированных процессов, при этом на каждом из n серверов окажется ровно 8 процессов. Однако, правила можно применять только последовательно, и поэтому объём оперативной памяти серверов накладывает ограничения на порядок применения правил.

По данному набору правил определите, в каком порядке нужно применить все 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» (без кавычек), а во второй — последовательность из 4n чисел от 1 до 4n, задающую номера правил в порядке их выполнения. Последовательность должна являться перестановкой, то есть включать каждое из чисел от 1 до 4n ровно по одному разу.

Если возможных ответов несколько, разрешается вывести любой.

Примеры
Входные данные
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
Выходные данные
YES
1 2 5 6 3 7 4 8
Входные данные
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
Выходные данные
YES
2 3 4 6 7 8 10 11 12 1 5 9
Примечание

(1) Чтобы быть предельно точными, следует сказать, что объём памяти сервера — 1 ГиБ = 1024 МиБ, а процессы требуют по 100 МиБ оперативной памяти, где гибибайт (ГиБ) — объём памяти в 230 байт, а мебибайт (МиБ) — объём памяти в 220 байт.

В первом тесте из условия сеть использует два сервера, на каждом из которых исходно запущено по четыре процесса. В соответствии с правилами репликации, каждый из процессов должен быть уничтожен и двукратно запущен на другом сервере. Один из возможных вариантов ответа представлен в условии: После исполнения правил 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.