76 - ZOJ 7th Anniversary Contest - G
It is the time for the 7th Internation Conference on Problem Collections (ICPC) to review submissions. The organizor has invited N professors to review M submitted papers. Each reviewer may first select K(<= M) papers that he/she would prefer to read. Then the organization committee will assign the papers to the reviewers according to the following rules:
1. Each paper will be assigned to exact 2 reviewers;
Now your job is to assign the papers so that as many papers that are reviewed as possible. It appears to be a quite complicated job. Can you help them?
Each case starts with two integers N and M, which are the number of reviewers and the number of papers, respectively. (1 <= N, M <= 177) Then N lines follow, each starts with a positive integer K and then K integers chosen from 1 to M, which are the indices of the papers chosen by this reviewer.
For each test case, first output a number indicating the number of papers are reviewed. Then output N lines. The i-th line contains the indices of the assigned papers to the i-th reviewer. The numbers must be in increasing order and be seperated by one space, and there must be no extra space at the end of the sequence. If there are multiply assignment leading to the greatest result, any one will be OK. A blank line should be added between test cases.
4 7 2 1 2 7 1 2 3 4 5 6 7 1 5 4 7 2 6 3 2 8 8 1 2 3 4 5 6 7 8 1 1
6 1 2 1 2 3 5 6 7 5 3 6 7 1 1 1
Author: CHEN, Yue
Source: ZOJ 7th Anniversary Contest