$N$ הפרות של Farmer John ($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$). הן לא חכמות עד כדי כך: סכום $K_{i}$ על כל הפרות $i$ לכל היותר $100,000$.

בלי שפה משותפת אי אפשר לדבר ישירות, אבל אפשר להעביר מסרים ולתרגם. $A$ ו־$B$ משוחחות אם ורק אם יש $T_{1}$, $T_{2}$, …, $T_{k}$ כך ש־$A$ ו־$T_{1}$ חולקות שפה, $T_{1}$ ו־$T_{2}$ גם, וכך עד $T_{k}$ ו־$B$.

Farmer John רוצה שכל פרה תתרועע עם כל אחרת. אפשר לקנות ספר כדי ללמד כל פרה כל שפה. כחסכן הוא רוצה מספר ספרים מזערי. מצאו:

• את מספר הספרים המזערי לקנייה.
• כל קבוצת ספרים מוקצית לפרות בכל סדר שתשיג את המטרה; תוכנית תבדוק את הפלט.

לדוגמה 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$ ייתן לכולן שפה משותפת ותקשורת.

אפשר במקום ללמדה $3$. אין שפה משותפת לכולן, אך Contessa יכולה לדבר עם Bessie דרך Alberta, הדוברת גם $3$. כל פתרון חלופי תקין יתקבל.

קלט

• שורה $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