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

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

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.

a) Add an arbitrary edge (x, y), provided that (x, y) does not exist before such an operation. Such an operation costs I

b) Delete an existing edge (x, y), which costs D

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.

Each test case starts with three integers, N, M

Two successive test cases are separated by a blank line. A case with N = 0, M

提交代码