{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eLong long ago, there was a prosperous kingdom which consisted of n cities and every two cites were connected by an undirected road.\u003cbr\u003e\u003cbr\u003eHowever, one day a big monster attacked the kingdom and some roads were destroyed. In order to evaluate the influence brought by the catastrophe, the king wanted to know the instability of his kingdom. Instability is defined as the number of the unstable subset of {1, 2,$\\cdots $,n}.\u003cbr\u003e\u003cbr\u003eA set S is unstable if and only if there exists a set A such that $A\\subseteq S(|A|\\geq 3$) and A is a \u003cb\u003eclique\u003c/b\u003e or an \u003cb\u003eindependent set\u003c/b\u003e, namely that cites in A are pairwise connected \u003cb\u003edirectly\u003c/b\u003e or they are pairwise disconnected.\u003cbr\u003e\u003cbr\u003eArchaeologist has already restored themroads that were not destroyed by the monster. And they want you to figure out the instability.\u003cbr\u003e\u003cbr\u003eSince the answer may be tremendously huge, you are only required to write a program that prints the answer modulo 1000000007.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains only one integer T, which indicates the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains two integers n ($3\\leq n \\leq 50$) and m ($1\\leq m\\leq n(n - 1)/2$), indicating the number of cities and the number of roads.\u003cbr\u003e\u003cbr\u003eThen the following are m lines, each of which contains two integers x and y, indicating there is a road between the city x and the city y.\u003cbr\u003e\u003cbr\u003eIt is guarenteed that there does not exist a road connecting the same city and there does not exist two same roads."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print a line “Case #x: y”, where x is the case number (starting from 1) and y is an integer indicating the instability modulo 1000000007."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4 3\r\n1 2\r\n2 3\r\n1 3\r\n3 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2\r\nCase #2: 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e\u0026amp;#8226; In the first example, {1,2,3} and {1,2,3,4} , containing the subset {1,2,3} which is connected\u003cbr\u003edirectly, are considered unstable.\u003cbr\u003e\u0026amp;#8226; In the second example, {1,2,3} is considered unstable because they are not pairwise connected\u003cbr\u003edirectly.\u003cbr\u003e"}}]}