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

Ограничение времени | 4 секунды
Ограничение памяти | 256 Мб
Ввод | стандартный ввод или input.txt
Вывод | стандартный вывод или output.txt

##

Максимальная оценка за эту задачу — 60 баллов, на проверку необходимо сдавать программу, решающую задачу

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

Всего в буфере накоплено 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 ≤ 100 1 \le n \le 100 1≤n≤100; 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.

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

Если введено недопустимое значение n — выведите -2.

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

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

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

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

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

## Пример

Ввод | Вывод
--- | ---
    3 3
    2 1
    1 3
    2
    1 2
    2
    1 3
    1 1
    3
    1
    2
    1 3