Lights

Bessie and the cows were playing games in the barn, but the power was reset and all the lights turned off. Help the cows turn every light back on so they can resume their games.

There are $N$ lights ($1 \le N \le 35$), numbered $1 \ldots N$. The lights and their switches are wired into a complex network with $M$ ($1 \le M \le 595$) connections, each joining a pair of lights.

Every light has a switch. Toggling a switch flips that light and all of the lights directly connected to it — each of them changes state (on becomes off, off becomes on).

Find the minimum number of switches you must toggle to turn all the lights back on.

It is guaranteed that at least one way to toggle the switches turns every light on.

• Line $1$: Two space-separated integers, $N$ and $M$.
• Lines $2 \ldots M+1$: Each line contains two space-separated integers, the two lights joined by a connection. No pair is repeated.

Print a single integer: the minimum number of switches that must be toggled to turn on all the lights.

There are 5 lights. Lights 1, 4, and 5 are each connected to both light 2 and light 3.

Toggle the switches on lights 1, 4, and 5.