1672 -- Fully Diversified Sequences of Sets

Language:

Fully Diversified Sequences of Sets

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 516		Accepted: 253		Special Judge

Description

Given a positive integer n, let N be the set of integers from 1 to n. A finite sequence A1, ..., Ak of subsets of N is fully diversified if:
a. Each subset Ai has an even number of elements.
b. For each element m in N, there are exactly m sets Ai in the sequence with m as a member.
For example, the sequence of subsets {1,3}, {2,3}, {2,3} is a fully diversified sequence of subsets of {1,2,3}. (Note that subsets in the sequence may be the same.)
A fully diversified sequence of subsets of N is minimal if no other fully diversified sequence of subsets of N has a smaller sequence count. The example above is minimal since the element 3 must occur in 3 different sets.
Write a program, which, given an integer n, determines whether there is a fully diversified sequence of subsets of the corresponding set N and, if there is a fully diversified sequence, finds a minimal fully diversified sequence of subsets of N.

Input

The input will be a sequence of positive integers n, one per line followed by a zero (0) (on another line) indicating the end of the input.

Output

If there is no fully diversified sequence of subsets of the corresponding set N, output a 0 on one line followed by a blank line.
If there is a fully diversified sequence of subsets of the corresponding set N, output the number of sets in your minimal sequence on one line, followed by the sets, one per line, followed by a blank line.
The elements of each set should be output in increasing order with a single space between numbers. The sets of sequences should be output in lexicographical order. There may be many possible solutions to each problem.

Sample Input

Sample Output

8
1 3 5 6 7 8
2 4 5 6 7 8
2 4 5 6 7 8
3 4 5 6 7 8
3 4 5 6 7 8
6 8
7 8
7 8

0

11
1 5 7 8 9 11
2 5 7 8 10 11
2 5 7 8 10 11
3 5 7 9 10 11
3 6 7 9 10 11
3 6 7 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
5 7 8 9 10 11

0

23
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
12 13 14 15 16 17 18 19 20 21 22 23
13 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
16 17 18 19 20 21 22 23
17 19 20 21 22 23
18 19 20 21 22 23
18 19 20 21 22 23
20 21 22 23
21 23
22 23
22 23

Source

Greater New York 2003