As $N$ vacas de Farmer John ($2 \le N \le 10,000$), numeradas $1..N$, falam $M$ línguas ($1 \le M \le 30,000$), numeradas $1..M$. A vaca $i$ fala $K_{i}$ línguas ($1 \le K_{i} \le M$): $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ ($1 \le L_{ij} \le M$). Não são assim tão inteligentes: a soma de $K_{i}$ sobre todas as vacas $i$ é no máximo $100,000$.

Sem língua comum não conversam diretamente, mas podem passar mensagens e traduzir. $A$ e $B$ conversam se e só se existe $T_{1}$, $T_{2}$, …, $T_{k}$ tal que $A$ e $T_{1}$ partilham uma língua, $T_{1}$ e $T_{2}$ também, e assim até $T_{k}$ e $B$.

Farmer John quer que cada vaca socialize com qualquer outra. Pode comprar livros para ensinar qualquer língua a qualquer vaca. Poupado, quer o mínimo de livros. Determine:

• O número mínimo de livros a comprar.
• Qualquer conjunto de livros atribuído a vacas, em qualquer ordem, que cumpra o objetivo; um programa avaliará a saída.

Exemplo: Alberta, Bessie, Contessa e línguas $1$, $2$, $3$. Alberta fala $2$ e $3$, Bessie $2$, Contessa $1$. As primeiras comunicam, Contessa está isolada.

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

Um livro para ensinar $2$ a Contessa dá a todas uma língua comum e comunicação.

Também pode ensinar-lhe $3$. Nem todas terão língua comum, mas é válido: Contessa comunica com Bessie através de Alberta, que também fala $3$. Qualquer outra solução válida será aceite.

Entrada

• Linha $1$: inteiros $N$ e $M$ separados por espaços.

• Linhas $2..N+1$: a linha $i+1$ descreve as línguas da vaca $i$ com $(K_i)+1$ inteiros $K_{i}$, $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ separados por espaços.

Saída

• Linha $1$: inteiro, número mínimo de livros.

• Linhas $2..B+1$: a linha $i+1$ contém dois inteiros separados por espaços, identificador da língua e da vaca que recebe o livro $i$. Se houver várias soluções, imprima qualquer uma.

Exemplos

Entrada 1

3 3
2 3 2
1 2
1 1

Saída 1

1
2 3

Autor do problema: Albert Gu, 2011