Les $N$ vaches de Farmer John ($2 \le N \le 10,000$), numérotées $1..N$, parlent $M$ langues ($1 \le M \le 30,000$), numérotées $1..M$. La vache $i$ connaît $K_{i}$ langues ($1 \le K_{i} \le M$) : $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ ($1 \le L_{ij} \le M$). Elles ne sont pas si intelligentes : la somme des $K_{i}$ sur toutes les vaches $i$ est au plus $100,000$.

Sans langue commune, deux vaches ne peuvent parler directement, mais peuvent transmettre des messages avec traduction si besoin. $A$ et $B$ peuvent discuter si et seulement si une suite $T_{1}$, $T_{2}$, …, $T_{k}$ existe : $A$ et $T_{1}$ partagent une langue, $T_{1}$ et $T_{2}$ aussi, et ainsi jusqu'à $T_{k}$ et $B$.

Farmer John souhaite que toute vache puisse discuter avec toute autre. Il peut acheter un livre pour enseigner n'importe quelle langue à n'importe quelle vache. Économe, il veut le minimum de livres. Déterminez :

• Le nombre minimal de livres à acheter.
• Une affectation quelconque de livres aux vaches, dans un ordre quelconque, atteignant le but ; un programme notera la sortie.

Exemple : Alberta, Bessie, Contessa et les langues $1$, $2$, $3$. Alberta parle $2$ et $3$, Bessie $2$, Contessa $1$. Les deux premières communiquent, Contessa est isolée.

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

Un livre enseignant $2$ à Contessa donne une langue commune à toutes et leur permet de communiquer.

On peut plutôt lui enseigner $3$. Sans langue commune à toutes, cela reste valide : Contessa parle à Bessie via Alberta, qui connaît aussi $3$. Toute autre solution valide sera acceptée.

Entrée

• Ligne $1$ : entiers $N$ et $M$ séparés par un espace.

• Lignes $2..N+1$ : la ligne $i+1$ décrit les langues de la vache $i$ avec $(K_i)+1$ entiers $K_{i}$, $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ séparés par des espaces.

Sortie

• Ligne $1$ : entier, nombre minimal de livres.

• Lignes $2..B+1$ : la ligne $i+1$ contient deux entiers séparés par un espace, identifiant de langue et identifiant de vache recevant le livre $i$. S'il y a plusieurs solutions, affichez-en une.

Exemples

Entrée 1

3 3
2 3 2
1 2
1 1

Sortie 1

1
2 3

Auteur du problème : Albert Gu, 2011