Le $N$ mucche di Farmer John ($2 \le N \le 10,000$), numerate $1..N$, parlano $M$ lingue ($1 \le M \le 30,000$), numerate $1..M$. La mucca $i$ parla $K_{i}$ lingue ($1 \le K_{i} \le M$): $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ ($1 \le L_{ij} \le M$). Non sono così intelligenti: la somma di $K_{i}$ per tutte le mucche $i$ è al massimo $100,000$.

Senza lingua comune non parlano direttamente, ma possono passare messaggi traducendo. $A$ e $B$ parlano se e solo se esiste $T_{1}$, $T_{2}$, …, $T_{k}$ tale che $A$ e $T_{1}$ condividono una lingua, $T_{1}$ e $T_{2}$ anche, e così fino a $T_{k}$ e $B$.

Farmer John vuole che ogni mucca socializzi con qualsiasi altra. Può comprare libri per insegnare qualsiasi lingua a qualsiasi mucca. Essendo parsimonioso, vuole il minimo di libri. Determina:

• Il numero minimo di libri da comprare.
• Qualsiasi insieme di libri assegnati alle mucche, in qualsiasi ordine, che raggiunga l'obiettivo; un programma valuterà l'output.

Esempio: Alberta, Bessie, Contessa e lingue $1$, $2$, $3$. Alberta parla $2$ e $3$, Bessie $2$, Contessa $1$. Le prime due comunicano, Contessa è isolata.

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

Un libro per insegnare $2$ a Contessa dà a tutte una lingua comune e comunicazione.

Può invece imparare $3$. Non tutte avranno lingua comune, ma è valido: Contessa comunica con Bessie tramite Alberta, che parla anche $3$. Qualsiasi altra soluzione valida sarà accettata.

Input

• Riga $1$: interi $N$ e $M$ separati da spazi.

• Righe $2..N+1$: la riga $i+1$ descrive le lingue della mucca $i$ con $(K_i)+1$ interi $K_{i}$, $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ separati da spazi.

Output

• Riga $1$: intero, numero minimo di libri.

• Righe $2..B+1$: la riga $i+1$ contiene due interi separati da spazi, identificativo della lingua e della mucca che riceve il libro $i$. Se ci sono più soluzioni, stampane una qualsiasi.

Esempi

Input 1

3 3
2 3 2
1 2
1 1

Output 1

1
2 3

Autore del problema: Albert Gu, 2011