Farmer John の $N$ 頭（$2 \le N \le 10,000$）は $1..N$ と番号が付き、$M$ 種（$1 \le M \le 30,000$）の言語（番号 $1..M$）を話します。牛 $i$ は $K_{i}$ 種（$1 \le K_{i} \le M$）、つまり $L_{i1}$、$L_{i2}$、…、$L_{iK_i}$（$1 \le L_{ij} \le M$）を話せます。そこまで賢くないので全牛 $i$ の $K_{i}$ の合計は高々 $100,000$ です。

共通言語がないと直接話せませんが、必要なら翻訳しつつ伝言できます。$A$ と $B$ が話せる必要十分条件は、$T_{1}$、$T_{2}$、…、$T_{k}$ が存在し、$A$ と $T_{1}$、$T_{1}$ と $T_{2}$ などが共通言語を持ち、最後に $T_{k}$ と $B$ も共通言語を持つことです。

全牛が他のどの牛とも交流できるようにしたいと考えています。本を買い、任意の牛に任意の言語を教えられます。倹約家なので最小の本数を望みます。求めるのは：

• 買う本の最小数。
• 目標を達成する本と牛の割り当てを任意の順に。プログラムが採点します。

例は Alberta、Bessie、Contessa と言語 $1$、$2$、$3$ です。Alberta は $2$、$3$、Bessie は $2$、Contessa は $1$ を話します。前の二頭は話せますが Contessa は孤立しています。

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

Contessa に $2$ を教える本を買うと、全牛が同じ言語を話し交流できます。

代わりに Contessa に $3$ を教えても有効です。共通言語はなくても、$3$ を話す Alberta を通じ Bessie と交流できます。他の有効な解も受理されます。

入力

• 第 $1$ 行：空白区切りの整数 $N$ と $M$。

• 第 $2..N+1$ 行：第 $i+1$ 行は牛 $i$ の言語を $(K_i)+1$ 個の空白区切りの整数 $K_{i}$、$L_{i1}$、$L_{i2}$、…、$L_{iK_i}$ で表します。

出力

• 第 $1$ 行：買う本の最小数を表す整数。

• 第 $2..B+1$ 行：第 $i+1$ 行は言語番号と本 $i$ を受け取る牛の番号の整数二つを空白区切りで与えます。複数解ならどれでも構いません。

入出力例

入力 1

3 3
2 3 2
1 2
1 1

出力 1

1
2 3

問題作成者：Albert Gu、2011