Упорядочивание транзакций
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

На вход данному модулю подается набор из $$$n$$$ транзакций, пронумерованных от $$$1$$$ до $$$n$$$. Транзакции исполняются в специальной виртуальной машине. Память данной машины состоит из $$$m$$$ локаций, пронумерованных от $$$1$$$ до $$$m$$$. Для каждой локации вам заранее известно множество локаций памяти, из которых данная транзакция производит чтения, и множество локаций памяти, в которые она производит запись. Для $$$i$$$-й транзакции обозначим эти множества как $$$RS_i$$$ и $$$WS_i$$$.

Из данного множества транзакций модуль должен выбрать некоторое подмножество и упорядочить его. Пусть модуль выбрал $$$k$$$ транзакций с номерами $$$p_1, p_2, \ldots, p_k$$$. Для возможности спекулятивного исполнения, в выбранной последовательности транзакций не должно быть конфликтов. Конфликтом называется пара транзакций, где та транзакция, которая идет раньше, записывает в некоторую локацию памяти, откуда потом читает другая транзакция. Более формально, транзакции $$$p_i$$$ и $$$p_j$$$ где $$$i < j$$$ конфликтуют, если существует такая локация памяти $$$l$$$, что $$$l \in WS_{p_i}$$$ и $$$l \in RS_{p_j}$$$.

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

Входные данные

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

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

Суммарный размер всех множеств $$$RS$$$ и $$$WS$$$ не превышает $$$10^6$$$.

Выходные данные

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

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

Система оценки

За каждый тест в данной задаче вы можете получить вещественное количество баллов от $$$0$$$ до $$$4$$$.

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

Всего в задаче $$$25$$$ тестов. Таким образом, получить $$$100$$$ баллов за данную задачу невозможно.

Пример

Входные данные

    3 31 1121 1231 131

Выходные данные

    2
    1 3