Farmer Johns $N$ Kühe ($2 \le N \le 10,000$), mit $1..N$ nummeriert, sprechen $M$ Sprachen ($1 \le M \le 30,000$), mit $1..M$ nummeriert. Kuh $i$ spricht $K_{i}$ Sprachen ($1 \le K_{i} \le M$): $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ ($1 \le L_{ij} \le M$). So klug sind sie nicht: Die Summe der $K_{i}$ über alle Kühe $i$ beträgt höchstens $100,000$.

Nur mit gemeinsamer Sprache spricht man direkt, aber Nachrichten können mit Übersetzung weitergegeben werden. $A$ und $B$ können genau dann sprechen, wenn eine Folge $T_{1}$, $T_{2}$, …, $T_{k}$ existiert: $A$ und $T_{1}$ teilen eine Sprache, $T_{1}$ und $T_{2}$ auch, und so weiter bis $T_{k}$ und $B$.

Farmer John möchte geselligere Kühe, sodass jede mit jeder anderen sprechen kann. Bücher können jeder Kuh jede Sprache beibringen. Sparsam möchte er möglichst wenige kaufen. Bestimme:

• Die minimale Anzahl benötigter Bücher.
• Eine beliebige erfolgreiche Zuweisung von Büchern an Kühe in beliebiger Reihenfolge; ein Programm bewertet die Ausgabe.

Beispiel: Alberta, Bessie, Contessa und Sprachen $1$, $2$, $3$. Alberta spricht $2$ und $3$, Bessie $2$, Contessa $1$. Die ersten beiden sprechen miteinander, Contessa ist allein.

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

Ein Buch für Sprache $2$ an Contessa gibt allen dieselbe Sprache und ermöglicht Kommunikation.

Alternativ kann sie $3$ lernen. Es gibt keine gemeinsame Sprache für alle, aber Contessa kann über Alberta, die auch $3$ spricht, mit Bessie sprechen. Andere gültige Lösungen werden ebenfalls akzeptiert.

Eingabe

• Zeile $1$: ganze Zahlen $N$ und $M$, durch Leerzeichen getrennt.

• Zeilen $2..N+1$: Zeile $i+1$ beschreibt die Sprachen von Kuh $i$ durch $(K_i)+1$ ganze Zahlen $K_{i}$, $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$, getrennt durch Leerzeichen.

Ausgabe

• Zeile $1$: ganze Zahl, minimale Anzahl der Bücher.

• Zeilen $2..B+1$: Zeile $i+1$ enthält zwei ganze Zahlen mit Leerzeichen: Sprachkennung und Kennung der Kuh, die Buch $i$ bekommt. Bei mehreren Lösungen ist jede erlaubt.

Beispiele

Eingabe 1

3 3
2 3 2
1 2
1 1

Ausgabe 1

1
2 3

Aufgabenautor: Albert Gu, 2011