{"raw_statement":[{"iden":"problem statement","content":"AtCoder Town has $N$ intersections and $M$ roads.  \nRoad $i$ connects Intersections $A_i$ and $B_i$.\nTakahashi, the mayor, has decided to install zero or more surveillance cameras at the intersections.  \nEach intersection can be installed with zero or one surveillance camera.\nHow many of the $2^N$ ways to install surveillance cameras monitor an even number of roads?\nHere, Road $i$ is said to be monitored when the following condition is satisfied:\n\n> a surveillance camera is installed at one or both of Intersections $A_i$ and $B_i$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 40$\n*   $1 \\leq M \\leq \\frac{N(N-1)}{2}$\n*   $1 \\leq A_i \\lt B_i \\leq N$\n*   $(A_i,B_i) \\neq (A_j,B_j)$ if $i \\neq j$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_M$ $B_M$"},{"iden":"sample input 1","content":"3 2\n1 2\n2 3"},{"iden":"sample output 1","content":"6\n\nThe sets of towns to install surveillance cameras to satisfy the condition are: ${ } , { 2 } , { 1,2 } ,{1,3},{2,3},{1,2,3}$.  \nNote that it is allowed to install no surveillance camera."},{"iden":"sample input 2","content":"20 3\n5 6\n3 4\n1 2"},{"iden":"sample output 2","content":"458752\n\nThe town may not be connected."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}