시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 17 7 4 50.000%

문제

선영이는 대형 병원에서 사용하는 인사 관리 프로그램을 만들고 있다. 가장 먼저 만들고 있는 부분은 직원들의 휴가 관리 프로그램이다.

병원에서 일하는 간호사는 두 종류가 있다. 일반 간호사는 입원해 있는 환자를 간호하는 간호사이고, 특수 간호사는 "수술 간호사", "간호부장"과 같이 특별히 맡은 자리가 있는 간호사이다.

일반 간호사가 휴가를 갔을 때는 다른 간호사가 그 간호사의 업무를 대신해 주면 되기 때문에, 큰 문제가 생기지 않는다. 하지만, 특수 간호사는 반드시 대체자가 있어야지만 휴가를 갈 수 있다. 따라서, 모든 특수 간호사는 자신을 대체할 수 있는 간호사의 목록을 가지고 있다. 만약, 대체 간호사도 특수 간호사인 경우에는 그 대체 간호사도 대체할 간호사를 찾아야 한다. 가끔, 특수 간호사는 대체를 할 수 없어서 휴가를 갈 수 없는 경우도 있다.

아래와 같은 예를 보자. 이 병원에는 총 일곱 명의 간호사가 있다. Alice, Bob, Clara, Dona, Emma는 특수 간호사이고, Fiona, Gloria는 일반 간호사이다. 누가 누구를 대체할 수 있는지는 아래 그림에 화살표로 나타나있다. (A에서 B로 가는 화살표는 A가 B를 대체할 수 있다는 의미)

위의 예제에서 Dona와 Emma는 휴가를 절대로 갈 수 없다. 그 이유는 서로가 서로를 대체하기 때문에, 한 명이 휴가를 갔을 때, 휴가를 가지 않은 한 사람이 두 업무를 동시에 맡을 수 없기 때문이다. Alice, Bob, Clara는 휴가에 갈 수 있다. 하지만, Gloria는 동시에 Bob과 Clara를 대체할 수 없기 때문에, Bob과 Clara는 동시에 휴가를 갈 수 없다.

간호사의 정보가 주어졌을 때, 휴가를 절대로 갈 수 없는 간호사와 휴가를 갈 수는 있지만, 동시에 휴가를 갈 수 없는 간호사의 쌍을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 간호사의 수 n과 특수 간호사의 수 k가 주어진다. 간호사 1번부터 k번까지는 특수 간호사, k+1번부터 n번까지는 일반 간호사이다. (1 ≤ k < n ≤ 1000)

다음 k개 줄에는 가능한 대체 정보가 주어진다. (i+1)번째 줄의 첫 번째 숫자는 i번 간호사를 대체할 수 있는 간호사의 수 di이다. 다음 di개의 숫자는 그 간호사를 대체할 수 있는 간호사의 번호이다. 전체 리스트의 길이는 10,000을 넘지 않는다.

출력

첫째 줄에 절대로 휴가를 갈 수 없는 간호사의 수를 출력하고, 다음 줄에는 그러한 간호사의 번호를 모두 출력한다.

다음 줄에는 휴가를 갈 수는 있지만, 동시에 휴가를 갈 수 없는 간호사 쌍의 수를 출력한다. 만약, 쌍의 수가 10,000보다 작거나 같다면, 다음 줄부터 한 줄에 하나씩 그러한 쌍을 출력한다. (쌍 (A,B)와 (B,A)는 같은 쌍이다)

예제 입력

7 5
2 6 7
1 7
2 2 7
1 5
1 4

예제 출력

2
4 5
3
2 3
2 7
3 7

힌트