SP5142 PAIRGRPH - A Pair of Graphs

Please click [here](http://www.spoj.com/content/john_jones:hangzhou2008.pdf) 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. - - - - - - MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], skipTags: ["script","noscript","style","textarea","code"] } }); 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.

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.

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