$N$ bò của Farmer John ($2 \le N \le 10,000$), đánh số $1..N$, thông thạo $M$ ngôn ngữ ($1 \le M \le 30,000$), đánh số $1..M$. Bò $i$ nói $K_{i}$ ngôn ngữ ($1 \le K_{i} \le M$): $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ ($1 \le L_{ij} \le M$). Bò không quá thông minh nên tổng $K_{i}$ trên mọi bò $i$ tối đa $100,000$.

Không có ngôn ngữ chung thì không nói trực tiếp, nhưng có thể truyền tin và dịch. $A$ và $B$ trò chuyện khi và chỉ khi có $T_{1}$, $T_{2}$, …, $T_{k}$ sao cho $A$ và $T_{1}$ chung ngôn ngữ, $T_{1}$ và $T_{2}$ cũng vậy, cứ thế tới $T_{k}$ và $B$.

Farmer John muốn mỗi bò giao tiếp với bất kỳ bò khác. Ông có thể mua sách dạy ngôn ngữ tùy ý cho bò tùy ý. Tiết kiệm, ông muốn ít sách nhất. Xác định:

• Số sách ít nhất cần mua.
• Một tập sách phân cho bò theo thứ tự bất kỳ đạt mục tiêu; chương trình sẽ chấm đầu ra.

Ví dụ Alberta, Bessie, Contessa và ngôn ngữ $1$, $2$, $3$. Alberta nói $2$ và $3$, Bessie $2$, Contessa $1$. Hai bò đầu giao tiếp được, Contessa riêng lẻ.

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

Sách dạy Contessa ngôn ngữ $2$ khiến mọi bò có chung ngôn ngữ và giao tiếp.

Cũng có thể dạy $3$. Không phải tất cả chung ngôn ngữ nhưng vẫn hợp lệ: Contessa nói với Bessie qua Alberta cũng biết $3$. Mọi phương án hợp lệ khác cũng được chấp nhận.

Dữ liệu vào

• Dòng $1$: số nguyên $N$ và $M$ cách nhau bởi dấu cách.

• Các dòng $2..N+1$: dòng $i+1$ mô tả ngôn ngữ bò $i$ với $(K_i)+1$ số nguyên $K_{i}$, $L_{i1}$, $L_{i2}$, …, $L_{iK_i}$ cách nhau bởi dấu cách.

Dữ liệu ra

• Dòng $1$: số nguyên là số sách ít nhất.

• Các dòng $2..B+1$: dòng $i+1$ chứa hai số nguyên cách nhau bởi dấu cách, mã ngôn ngữ và mã bò nhận sách $i$. Có nhiều lời giải thì in bất kỳ.

Ví dụ

Dữ liệu vào 1

3 3
2 3 2
1 2
1 1

Dữ liệu ra 1

1
2 3

Tác giả bài toán: Albert Gu, 2011