{"problem":{"name":"K. Vertex Covers","description":{"content":"In graph theory, a vertex cover of a graph $G$ is a set of vertices $S$ such that each edge of the graph is incident to at least one vertex of the set. That is to say, for every edge $(u, v)$ of the g","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10222K"},"statements":[{"statement_type":"Markdown","content":"In graph theory, a vertex cover of a graph $G$ is a set of vertices $S$ such that each edge of the graph is incident to at least one vertex of the set. That is to say, for every edge $(u, v)$ of the graph, either $u$ or $v$ is in the vertex cover $S$.\n\nNow, Kamilah shows you an undirected graph $G$ without loops or multiple edges, each vertex of which has a weight. She can evaluate a vertex cover $S$ of $G$ by the product of weights of all vertices belonging to $S$. Here, the product of an empty set (of numbers) is defined as $1$.\n\nYou are asked to calculate the sum of the evaluations described above for all vertex covers of $G$.\n\nThe input contains several test cases, and the first line is an integer $T$ indicating the number of test cases which is up to $3600$.\n\nFor each test case, the first line contains three integers $n med (1 <= n <= 36)$ and $m med (0 <= m <= frac(n (n -1), 2))$ which are the number of vertices and the number of edges in the graph $G$, and $q med (10^8 <= q <= 10^9)$ which is a prime number for the output.\n\nThe second line contains $n$ integers, the $i$-th of which is the weight of the $i$-th vertices in $G$. All weights are in the range of $1$ to $10^9$.\n\nEach of the following $m$ lines contains two integers $u$ and $v med (1 <= u, v <= n)$ describing an edge between the $u$-th vertex and the $v$-th one.\n\nWe guarantee that no more than $36$ test cases satisfy $n > 18$.\n\nFor each test case, output a line containing _Case #x: y_, where _x_ is the test case number starting from $1$, and _y_ is the remainder of the answer dividing by $q$.\n\n## Input\n\nThe input contains several test cases, and the first line is an integer $T$ indicating the number of test cases which is up to $3600$.For each test case, the first line contains three integers $n med (1 <= n <= 36)$ and $m med (0 <= m <= frac(n (n -1), 2))$ which are the number of vertices and the number of edges in the graph $G$, and $q med (10^8 <= q <= 10^9)$ which is a prime number for the output.The second line contains $n$ integers, the $i$-th of which is the weight of the $i$-th vertices in $G$. All weights are in the range of $1$ to $10^9$.Each of the following $m$ lines contains two integers $u$ and $v med (1 <= u, v <= n)$ describing an edge between the $u$-th vertex and the $v$-th one.We guarantee that no more than $36$ test cases satisfy $n > 18$.\n\n## Output\n\nFor each test case, output a line containing _Case #x: y_, where _x_ is the test case number starting from $1$, and _y_ is the remainder of the answer dividing by $q$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $, and no loops or multiple edges.  \nLet $ w: V \\to \\mathbb{Z}^+ $ be a weight function on vertices, with $ w_i $ denoting the weight of vertex $ i $.  \nLet $ \\mathcal{S} $ be the set of all vertex covers of $ G $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 36 $, $ 0 \\le m \\le \\frac{n(n-1)}{2} $  \n2. $ 10^8 \\le q \\le 10^9 $, $ q $ prime  \n3. $ 1 \\le w_i \\le 10^9 $ for all $ i \\in V $  \n4. At most 36 test cases have $ n > 18 $  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{S \\in \\mathcal{S}} \\prod_{v \\in S} w_v \\mod q\n$$  \nwhere the product over the empty set is defined as 1.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10222K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}