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$도 그러한 것입니다.

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와 대화할 때 $3$도 아는 Alberta를 거칠 수 있습니다. 다른 모든 유효한 대안도 인정합니다.

입력

• $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