{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv id\u003d\"problem-body\"\u003e \n \u003cp\u003e \u003c/p\u003e \n \u003cp\u003eYou are given an undirected graph G(V, E). Each vertex has a mark which is an integer from the range [0..2\u003csup\u003e31\u003c/sup\u003e – 1]. Different vertexes may have the same mark.\u003c/p\u003e \n \u003cp\u003eFor an edge (u, v), we define Cost(u, v) \u003d mark[u] xor mark[v].\u003c/p\u003e \n \u003cp\u003eNow we know the marks of some certain nodes. You have to determine the marks of other nodes so that the total cost of edges is as small as possible.\u003c/p\u003e \n \u003cp\u003e\u003c/p\u003e \n \u003ch3\u003eInput\u003c/h3\u003e \n \u003cp\u003eThe first line of the input data contains integer \u003cb\u003eT\u003c/b\u003e (1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 10) - the number of testcases. Then the descriptions of T testcases follow.\u003c/p\u003e \n \u003cp\u003eFirst line of each testcase contains 2 integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eM\u003c/b\u003e (0 \u0026lt; \u003cb\u003eN\u003c/b\u003e \u0026lt;\u003d 500, 0 \u0026lt;\u003d \u003cb\u003eM\u003c/b\u003e \u0026lt;\u003d 3000). \u003cb\u003eN\u003c/b\u003e is the number of vertexes and \u003cb\u003eM\u003c/b\u003e is the number of edges. Then \u003cb\u003eM\u003c/b\u003e lines describing edges follow, each of them contains two integers u, v representing an edge connecting u and v.\u003c/p\u003e \n \u003cp\u003eThen an integer \u003cb\u003eK\u003c/b\u003e, representing the number of nodes whose mark is known. The next \u003cb\u003eK\u003c/b\u003e lines contain 2 integers u and p each, meaning that node u has a mark p. It’s guaranteed that nodes won’t duplicate in this part.\u003c/p\u003e \n \u003ch3\u003eOutput\u003c/h3\u003e \n \u003cp\u003eFor each testcase you should print \u003cb\u003eN\u003c/b\u003e lines integer the output. The \u003cb\u003eK\u003c/b\u003eth line contains an integer number representing the mark of node \u003cb\u003eK\u003c/b\u003e. If there are several solutions, you have to output the one which minimize the sum of marks. If there are several solutions, just output any of them.\u003c/p\u003e \n \u003ch3\u003eExample\u003c/h3\u003e \n \u003cpre\u003e\n\u003cb\u003eInput:\u003c/b\u003e\n1\n3 2\n1 2\n2 3\n2\n1 5\n3 100\n\n\u003cb\u003eOutput:\u003c/b\u003e\n5\n4\n100 \n\u003c/pre\u003e \n \u003c/div\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Translation","value":{"format":"HTML","content":"给出一个无向图,每个点有一个标号mark[i],不同点可能有相同的标号。对于一条边(u, v),它的权值定义为mark[u] xor mark[v]。现在一些点的标号已定,请决定剩下点的标号,使得总的边权和最小。(0 \u003c N \u003c\u003d 500, 0 \u003c\u003d M \u003c\u003d 3000, 0 \u003c\u003d mark[i] \u003c\u003d 2^31-1)"}}]}