A Pair of Graphs

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

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 IA and IB on two graphs, respectively.
b) Delete an existing edge (x, y), which costs DA and DB on two graphs,respectively.

Input

There are multiple test cases in the input file.
Each test case starts with three integers, N, MA and MB, ( 1 ≤ N ≤ 8, 0 ≤ MB ,MA ≤ 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 IA, IB, DA, and DB come next, (0 ≤ IA, IB, DA, DB ≤ 32767 ), representing the costs as stated in the problem description. The next MA + MB 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, MA = 0,and MB = 0 indicates the end of the input file, and should not be processed by your program.

Output

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

Sample Input

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

Sample Output

Case #1: 0 Case #2: 1

Hint

lcy

Source

2008 Asia Regional Hangzhou

提交代码