Set Partitions

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Let us consider the set of n first integer numbers: Nn = {1, 2, ......, n}. The partition is the representation of this set as a union of one or more non-empty disjoint sets. The examples of the partitions for n = 5 are:

      There are totally 52 partitions of the set N5 . Note that we do not distinguish between partitions that only differ by the order of the united sets. 

      We can order Nn partitions in the lexicographical order. To define this order we first introduce lexicographical order on the subsets of Nn. We say that the set A ⊂ Nn is lexicographically smaller than the set B ⊂ Nn and write A < B if one of the following is true: 

      It is clear that the relation introduced is the total order on all subsets of Nn.
      In other words, A is lexicographically less than B as a sequence if written in the increasing order.
      Now we define the canonical representation of the partition as the representation in which the united
sets are ordered lexicographically.
      The partitions are ordered lexicographically in the following way. The partition Nn = A1 ∪ A2 ∪...... ∪ Ais lexicographically smaller than the partion Nn = B1 ∪ B2 ∪......∪ Bif there is such i that A1 = B1,A2 = B2, . . . , Ai-1 = Bi-1 and Ai < Bi.
      Given the partition of Nyou have to find the next partition in the lexicographical order.

Input

      The input file contains several tests cases. Each test case is the the canonical representation of the partition. The first line of the test case contains n and k — the number of elements in the partitioned set and the number of parts in a partition (1 ≤ n ≤ 200). The following k lines contain elements of the partition. Elements of each set are sorted in the increasing order.
      Test cases are separated from each other with blank lines. The last line of the output file contains two zeroes. This case must not be processed. 
      The sum of n in all testcases of the input file doesn’t exceed 2000.

Output

      For each test case output the next partition in the lexicographical order. If the partition in the input file is the last one, output the first in lexicographical order partition. Use the same format as the input file. Separate output for test cases by a blank line.

Sample Input

5 2
1 2 3
4 5

5 2
1 3 5
2 4

5 1
1 2 3 4 5

5 5
1
2
3
4
5

0 0

Sample Output

5 2
1 2 3 4

5
5 4
1 4
2
3
5

5 2
1 2 3 5
4

5 4
1
2
3
4 5

Hint

注意格式

Source

Andrew Stankevich Contest 16

Manager

Information
Solved Number2
Submit Number5
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel