A Pair of Graphs

We say that two graphs are equivalent if and only if a one-to-one correspondence between their nodes can be established and under such a correspondence their edges are exactly the same. Given A and B, two undirected simple graphs with the same number of vertexes, you are to find a series of operations with the minimum cost that will make the two graphs equivalent. An operation may be one of the following two types:
a) Add an arbitrary edge (x, y), provided that (x, y) does not exist before such an operation. Such an operation costs I_A and I_B on two graphs, respectively.
b) Delete an existing edge (x, y), which costs D_A and D_B on two graphs,respectively.

There are multiple test cases in the input file.
Each test case starts with three integers, N, M_A and M_B, ( 1 ≤ N ≤ 8, 0 ≤ M_B ,M_A ≤ N*(N-1)/2 ), the total number of vertexes, the number of edges in graph A,and the number of edges in graph B, respectively. Four integers I_A, I_B, D_A, and D_B come next, (0 ≤ I_A, I_B, D_A, D_B ≤ 32767 ), representing the costs as stated in the problem description. The next M_A + M_B lines describe the edges in graph A followed by those in graph B. Each line consists of exactly two integers, X and Y ( X ≠ Y , 0 ≤ X,Y < N).
Two successive test cases are separated by a blank line. A case with N = 0, M_A = 0,and M_B = 0 indicates the end of the input file, and should not be processed by your program.

Please print the minimum cost in the format as illustrated below.

1 0 0
1 2 3 7

4 2 3
1 6 5 1
0 1
0 3
0 2
1 2
1 0

0 0 0

Case #1: 0
Case #2: 1

2008 Asia Regional Hangzhou