# Транзакции - 2

##

Максимальная оценка за эту задачу — 40 баллов.

В этой задаче n = 10000 n = 10000 n=10000. Условие задачи и форматы ввода и вывода полностью совпадают с предыдущей задачей, однако в этой задаче вам необходимо сдать на проверку текстовый файл с ответом на конкретный тест, который вы должны сгенерировать на своем компьютере. Скачать файл со входными данными для этой задачи вы можете нажав на ссылку "Скачать условие задачи" внизу этой страницы (после раздела "Система оценивания").

Во время тура ответ будет проверяться только на соответствие формату, проверка с выставлением баллов будет осуществляться после окончания тура. Статус OK и 0 баллов во время тура означает, что сданный вами файл соответствует формату и будет проверен после тура, в случае других статусов файл не соответствует формату и вам следует проверить и исправить его.

Для ускорения работы файловой системы на сервере необходимо накапливать операции ввода-вывода (транзакции) в буфере, а затем выполнять их.

Всего в буфере накоплено n n n транзакций, пронумерованных от 1 1 1 до n n n. Память сервера состоит из m m m участков, пронумерованных от 1 1 1 до m m m. Для каждой транзакции известно множество участков памяти, из которых данная транзакция производит чтение, и множество участков памяти, в которые она производит запись. Для i i i-й транзакции обозначим эти множества как R S i RS_i R S i​ и W S i WS_i W S i​.

Из заданного множества транзакций нужно выбрать некоторое подмножество и упорядочить транзакции внутри него.

Пусть было выбрано упорядоченное подмножество (последовательность) из k k k транзакций с номерами p 1 , p 2 , … , p k p_1, p_2, \ldots, p_k p 1​,p 2​,…,p k​. В выбранной последовательности транзакций не должно быть конфликтов. Конфликтом называется пара транзакций, в которой более ранняя транзакция записывает данные в область памяти, из которого затем читает другая транзакция. Более формально, транзакции p i p_i p i​ и p j p_j p j​, где i < j i < j i<j, конфликтуют, если существует такой участок памяти l l l, что l ∈ W S p i l \in WS_{p_i} l∈W S p i​​ и l ∈ R S p j l \in RS_{p_j} l∈R S p j​​.

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

## Формат ввода

В первой строке вводятся два целых числа n n n и m m m — количество транзакций и участков памяти соответственно ( 1 ≤ n ≤ 10000 1 \le n \le 10000 1≤n≤10000; 1 ≤ m ≤ 1 0 6 1 \le m \le 10^6 1≤m≤1 0 6). Далее следуют описания транзакций в порядке возрастания номеров.

Каждое описание транзакции содержит три строки. Первая из них содержит два целых числа r i r_i r i​ и w i w_i w i​ — размеры множеств R S i RS_i R S i​ и W S i WS_i W S i​ соответственно ( 1 ≤ r i , w i ≤ m 1 \le r_i, w_i \le m 1≤r i​,w i​≤m). Вторая строка содержит r i r_i r i​ различных целых чисел — элементы множества R S i RS_i R S i​. Третья строка содержит w i w_i w i​ различных целых чисел — элементы множества W S i WS_i W S i​.

Суммарный всех r i + w i r_i + w_i r i​+w i​ по всем i i i не превышает 1 0 6 10^6 1 0 6.

## Формат вывода

В первой строке выведите число k k k — количество транзакций в выбранной последовательности.

Во второй строке выведите k k k различных целых чисел — номера транзакций в порядке их выполнения.

## Система оценивания

Если выведенная вами последовательность содержит конфликтующие транзакции, вы получите 0 0 0 баллов за тест. В противном случае, вы получите 40 k n \frac{40k}{n} n 40 k​ баллов.