Adrian al III-lea este un prinț vrăjitor. De 4 noiembrie, ziua vrăjitoriei, acesta a vrut să o impresioneze pe Norela, fata visurilor lui. El are n cărți de joc, care inițial se află înșirate pe o masă cu fața în jos. Adrian are la dispoziție m magii, o magie fiind de forma: q a1 a2 …, aq. În timpul unei magii, se vor întoarce pe rând şi în ordine cărțile cu indicii a1 a2 …, aq. (numerele sunt distincte două câte două). Cartea va fi întoarsă indiferent dacă aceasta se află cu fața în sus sau cu fața în jos (dacă este cu fața în sus, se va întoarce cu fața în jos, iar dacă este cu fața în jos se va întoarce cu fața în sus), iar fiecare magie poate fi utilizată maxim o dată. Ajutați-l pe Adrian să o impresioneze pe Norela înaintea dușmanului său, Manea cel Sprâncenat!

Cerința

Aflați numărul minim de magii ce trebuie folosite, astfel încât la final toate cărțile să fie cu fața în sus. De asemenea, spuneți și care magii au fost folosite. În cazul în care există mai multe soluții, se va afișa cea minim lexicografică.

Date de intrare

Fișierul de intrare norela.in conține pe prima linie două numere naturale n și m. Pe următoarele
m linii sunt descrise magiile astfel: q a1 a2 …, aq, unde q este numărul de cărți ce vor fi întoarse în cadrul acelei magii, iar a1 a2 …, aq reprezintă indicii acestor cărți.

Date de ieșire

Fișierul de ieșire norela.out va conține pe prima linie un singur număr natural reprezentând numărul minim de magii ce vor fi folosite, iar pe a doua linie vor fi enumerați indicii acestor magii. Dacă există mai multe soluții cu număr minim de magii se va afișa cea minim lexicografică.

Restricții și precizări

• se garantează că întotdeauna există soluție.
• pentru 20 de puncte n ≤ 40, m ≤ 18.
• pentru alte 30 de puncte n ≤ 50, m ≤ 21.
• pentru alte 25 de puncte n ≤ 60, m ≤ 22.
• pentru alte 25 de puncte n ≤ 60, m ≤ 24.
• problema a fost modificată pentru a putea fi rezolvată pe site. Datele se vor citi din fișier și limita de memorie este mai mică față de original (512 MB).

Exemplu:

norela.in

5 6
3 1 3 4
2 3 5
2 2 3
3 1 2 5
1 1
4 1 2 3 4

norela.out

3
1 2 3

Explicație

Folosirea magiilor cu indicii 1, 2 și 3 (1 3 4, 3 5 și 2 3) determină întoarcerea tuturor cărților pe față. Se observă că o altă soluție tot cu număr minim ar fi fost alegerea magiilor cu indicii 1, 4 și 5, dar aceasta este mai mare lexicografic decât cea din urmă.