HDU1016 DFS Prime Ring Problem

                              time limit: 4000/2000 ms (java/others) memory limit: 65536/32768 k (java/others)

                                                total submission(s): 14601 accepted submission(s): 6667

problem description

a ring is compose of n circles as shown in diagram. put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

note: the number of first circle should always be 1.

input

n (0 < n < 20).

output

the output format is shown as sample below. each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. the order of numbers must satisfy the above requirements. print solutions in

lexicographical order.

you are to write a program that completes above process.

print a blank line after each case.

sample input

6

8

sample output

case 1:

1 4 3 2 5 6

1 6 5 2 3 4

case 2:

1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

source

asia 1996, shanghai (mainland china)

recommend

jgshining

題解：典型dfs 做法已經标記在 程式上了