$N$ krów Farmer John ($2 \le N \le 10,000$), numerowanych $1..N$, mówi w $M$ językach ($1 \le M \le 30,000$), numerowanych $1..M$. Krowa $i$ zna $K_{i}$ języków ($1 \le K_{i} \le M$): $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ ($1 \le L_{ij} \le M$). Nie są aż tak mądre: suma $K_{i}$ po wszystkich krowach $i$ wynosi najwyżej $100,000$.

Bez wspólnego języka nie rozmawiają bezpośrednio, ale mogą przekazywać wiadomości z tłumaczeniem. $A$ i $B$ rozmawiają wtedy i tylko wtedy, gdy istnieje $T_{1}$, $T_{2}$, …, $T_{k}$: $A$ i $T_{1}$ mają wspólny język, $T_{1}$ i $T_{2}$ też, i tak aż do $T_{k}$ i $B$.

Farmer John chce, aby każda krowa rozmawiała z każdą inną. Książka może nauczyć dowolną krowę dowolnego języka. Oszczędny chce minimalnej liczby książek. Wyznacz:

• Minimalną liczbę kupowanych książek.
• Dowolny skuteczny zestaw książek przydzielonych krowom w dowolnej kolejności; program oceni wyjście.

Przykład: Alberta, Bessie, Contessa i języki $1$, $2$, $3$. Alberta zna $2$ i $3$, Bessie $2$, Contessa $1$. Pierwsze dwie rozmawiają, Contessa jest sama.

                   #1   #2   #3
       Alberta           x    x
       Bessie            x
       Contessa     x

Książka ucząca Contessa języka $2$ daje wszystkim wspólny język i komunikację.

Można zamiast tego nauczyć ją $3$. Nie każda zna ten sam język, ale Contessa rozmawia z Bessie przez Alberta, znającą też $3$. Inne poprawne rozwiązania także będą przyjęte.

Wejście

• Wiersz $1$: całkowite $N$ i $M$ oddzielone spacjami.

• Wiersze $2..N+1$: wiersz $i+1$ opisuje języki krowy $i$ za pomocą $(K_i)+1$ całkowitych $K_{i}$, $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ oddzielonych spacjami.

Wyjście

• Wiersz $1$: całkowite, minimalna liczba książek.

• Wiersze $2..B+1$: wiersz $i+1$ zawiera dwa całkowite oddzielone spacjami: identyfikator języka i krowy otrzymującej książkę $i$. Przy wielu rozwiązaniach wypisz dowolne.

Przykład

Wejście 1

3 3
2 3 2
1 2
1 1

Wyjście 1

1
2 3

Autor zadania: Albert Gu, 2011