PAIRGRPH - A Pair of Graphs


Please click here to download a PDF version of the contest problems. The problem is problem A in the PDF. Remember that you must use stdin/stdout at SPOJ.


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:

  • 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.
  • Delete an existing edge ($x$, $y$), which costs $D_A$ and $D_B$ on two graphs, respectively.

Input

There are multiple test cases in the input file.

Each test case starts with three integers, $N$, $M_A$ and $M_B$, ($1 \le N \le 8$, $0 \le M_A, M_B \le \frac{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 \le I_A, I_B, D_A, D_B \le 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 \ne Y$, $0 \le 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.

Output

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

Example

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

Output for the Sample Input
Case #1: 0
Case #2: 1

hide comments
devil: 2015-05-01 18:48:12

i don't get it......how is the answer for test case 2 equal to 1....????

:D: 2012-11-29 09:06:51

It can be a browser fault. File is there and in the worst case you can save it and open from a folder.
Reply : got the file :)

Last edit: 2012-11-29 20:04:16
Piyush Kumar: 2012-11-28 21:40:55

The link isn't opening!


Added by:Fudan University Problem Setters
Date:2009-11-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C99 GOSU NODEJS OBJC PERL6 VB.NET
Resource:ACM/ICPC Regional Contest, Hangzhou 2008