{"problem":{"name":"Security Camera","description":{"content":"AtCoder Town has $N$ intersections and $M$ roads.   Road $i$ connects Intersections $A_i$ and $B_i$. Takahashi, the mayor, has decided to install zero or more surveillance cameras at the intersections","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc220_h"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc220_h","tags":[],"sample_group":[["3 2\n1 2\n2 3","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."],["20 3\n5 6\n3 4\n1 2","458752\n\nThe town may not be connected."]],"created_at":"2026-03-03 11:01:14"}}