F. Кошмар Евклида
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

В своем плохом сне, у Евклида был набор $$$S$$$ из $$$n$$$ $$$m$$$-мерных векторов над полем $$$\mathbb{Z}_2$$$, и он мог их складывать. Другими словами, у него были вектора с $$$m$$$ координатами, каждая координата равнялась либо $$$0$$$, либо $$$1$$$. Сложение векторов определяется следующим образом: пусть $$$u+v = w$$$, тогда $$$w_i = (u_i + v_i) \bmod 2$$$.

Евклид может сложить любое подмножество векторов из $$$S$$$ и сохранить получившийся $$$m$$$-мерный вектор над $$$\mathbb{Z}_2$$$. В частности, он может сложить пустое подмножество векторов. В таком случае, все координаты получившегося вектора будут равны $$$0$$$.

Пусть $$$T$$$ будет множеством всех векторов, которые могут быть получены как сумма некоторого подмножества векторов из $$$S$$$. Теперь Евклид интересуется, каков размер $$$T$$$, и может ли он использовать только какое-то подмножество $$$S'$$$ множества $$$S$$$, чтобы получить все вектора из $$$T$$$. Как всегда и бывает в таких ситуациях, он не проснется до тех пор, пока не выяснит это. Пока что дела для философа обстоят довольно мрачно. Однако, появилась надежда, когда он заметил, что все вектора из $$$S$$$ содержат максимум $$$2$$$ координаты, равные $$$1$$$.

Помогите Евклиду вычислить $$$|T|$$$, количество $$$m$$$-мерных векторов над $$$\mathbb{Z}_2$$$, которые могут быть получены как сумма какого-то подмножества векторов из $$$S$$$. Так как оно может быть довольно велико, выведите его по модулю $$$10^9+7$$$. Также, вы должны найти $$$S'$$$, минимальное такое подмножество $$$S$$$, что все вектора из $$$T$$$ могут быть получены как как сумма какого-то подмножества векторов из $$$S'$$$. В случае, если существует несколько таких подмножеств с минимальным количеством элементов, выведите лексикографически минимальный по индексам взятых элементов.

Рассмотрим два множества $$$A$$$ и $$$B$$$, такие что $$$|A| = |B|$$$. Пусть $$$a_1, a_2, \dots a_{|A|}$$$ и $$$b_1, b_2, \dots b_{|B|}$$$ будут возрастающие массивы индексов элементов, взятых в $$$A$$$ и в $$$B$$$, соответственно. $$$A$$$ лексикографически меньше, чем $$$B$$$, если существует такое $$$i$$$, что $$$a_j = b_j$$$ для всех $$$j < i$$$ и $$$a_i < b_i$$$.

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

В первой строке даны два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 5 \cdot 10^5$$$), обозначающие количество векторов в $$$S$$$ и количество измерений.

В следующих $$$n$$$ строках дано описание векторов из $$$S$$$. В каждой из них дано целое число $$$k$$$ ($$$1 \leq k \leq 2$$$), а затем $$$k$$$ различных целых чисел $$$x_1, \dots x_k$$$ ($$$1 \leq x_i \leq m$$$). Это обозначает $$$m$$$-мерный вектор, у которого координаты номер $$$x_1, \dots x_k$$$ равны $$$1$$$, а все остальные координаты равны $$$0$$$.

Среди этих $$$n$$$ векторов нет одинаковых.

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

В первой строке выведите два целых числа: остаток от деления $$$|T|$$$ на $$$10^9+7$$$, и $$$|S'|$$$. Во второй строке выведите $$$|S'|$$$ целых чисел — индексы элементов, входящих в $$$S'$$$, в возрастающем порядке. Элементы $$$S$$$ нумеруются с $$$1$$$ в порядке, в котором они даны во входных данных.

Примеры
Входные данные
3 2
1 1
1 2
2 2 1
Выходные данные
4 2
1 2
Входные данные
2 3
2 1 3
2 1 2
Выходные данные
4 2
1 2
Входные данные
3 5
2 1 2
1 3
1 4
Выходные данные
8 3
1 2 3
Примечание

В первом примере нам даны три вектора:

  • $$$10$$$
  • $$$01$$$
  • $$$11$$$

Оказывается, что мы может представить все вектора из $$$2$$$-мерного пространства используя эти вектора:

  • $$$00$$$, сумма пустого подмножества векторов;
  • $$$01 = 11 + 10$$$, сумма первого и третьего векторов;
  • $$$10 = 10$$$, просто первый вектор;
  • $$$11 = 10 + 01$$$, сумма первого и второго векторов.

Поэтому, $$$T = \{00, 01, 10, 11\}$$$. Мы можем выбрать любые два из трех векторов $$$S$$$, и все еще будем способны получить все вектора из $$$T$$$. В таком случае, мы выберем два первых вектора. Так как мы не можем получить все вектора из $$$T$$$, используя только один вектор из $$$S$$$, $$$|S'| = 2$$$ и $$$S' = \{10, 01\}$$$ (индексы $$$1$$$ и $$$2$$$), как множество $$$\{1, 2 \}$$$ — лексикографически минимально. Мы можем получить все вектора из $$$T$$$, используя только вектора из $$$S'$$$, как показано ниже:

  • $$$00$$$, сумма пустого подмножества;
  • $$$01 = 01$$$, просто второй вектор;
  • $$$10 = 10$$$, просто первый вектор;
  • $$$11 = 10 + 01$$$, сумма первого и второго вектора.