Las $N$ vacas de Farmer John ($2 \le N \le 10,000$), numeradas $1..N$, hablan $M$ idiomas ($1 \le M \le 30,000$), numerados $1..M$. La vaca $i$ habla $K_{i}$ idiomas ($1 \le K_{i} \le M$): $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ ($1 \le L_{ij} \le M$). No son tan inteligentes: la suma de $K_{i}$ sobre todas las vacas $i$ es como máximo $100,000$.
Sin idioma común no hablan directamente, pero pueden pasar mensajes y traducir. $A$ y $B$ pueden conversar si y solo si existe $T_{1}$, $T_{2}$, …, $T_{k}$ tal que $A$ y $T_{1}$ comparten idioma, $T_{1}$ y $T_{2}$ también, y así hasta $T_{k}$ y $B$.
Farmer John quiere que cada vaca socialice con cualquier otra. Puede comprar libros para enseñar cualquier idioma a cualquier vaca. Como es ahorrador, quiere el mínimo de libros. Determina:
- El número mínimo de libros que comprar.
- Cualquier conjunto de libros asignados a vacas en cualquier orden que cumpla el objetivo; un programa calificará la salida.
Ejemplo: Alberta, Bessie, Contessa e idiomas $1$, $2$, $3$. Alberta habla $2$ y $3$, Bessie $2$, Contessa $1$. Las dos primeras se comunican, Contessa está aislada.
#1 #2 #3
Alberta x x
Bessie x
Contessa xUn libro para enseñar $2$ a Contessa da a todas un idioma común y comunicación.
También puede enseñarle $3$. No todas tendrán el mismo idioma, pero sigue siendo válido: Contessa habla con Bessie a través de Alberta, que también habla $3$. Se aceptará cualquier otra solución válida.
Entrada
Línea $1$: enteros $N$ y $M$ separados por espacios.
Líneas $2..N+1$: la línea $i+1$ describe los idiomas de la vaca $i$ con $(K_i)+1$ enteros $K_{i}$, $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ separados por espacios.
Salida
Línea $1$: entero, mínimo número de libros.
Líneas $2..B+1$: la línea $i+1$ contiene dos enteros separados por espacios, el identificador de idioma y el de la vaca que recibe el libro $i$. Si hay varias soluciones, imprime cualquiera.
Ejemplos
Entrada 1
3 3 2 3 2 1 2 1 1
Salida 1
1 2 3
Autor del problema: Albert Gu, 2011