Minimum Switch Presses for Alarm Clock

An intricate alarm clock circuit is controlled by a number of switches. The peculiarity of this circuit is that each switch is connected to some other switches. When a switch is toggled (pressed), it only toggles the state of all the switches directly connected to it, but not its own state. Initially, all switches are turned on. The alarm clock stops only if all switches are off.

Your task is to determine the minimum number of switch presses needed to turn all switches off. If no matter how you press the switches the alarm clock cannot be stopped, output Change an alarm clock, please!.

Mathematically, if we denote the state of a switch as 1 (on) or 0 (off) and let \(x_i\) be 1 if switch \(i\) is pressed and 0 otherwise, then for each switch \(i\) with a set of neighbors \(N(i)\) the final state is determined by:

[ state(i)=1+\sum_{j\in N(i)} x_j ; (\bmod;2). ]

You need \(state(i)=0\) for all \(i\), which gives the system of equations:

[ \sum_{j\in N(i)} x_j \equiv 1 ; (\bmod;2), \quad \text{for } i=1,2,\dots,n. ]

Due to the potential complexity of inter-connections, note that the system may have no solution. In that case, output the message exactly as specified.

inputFormat

The input begins with two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of switches and \(m\) is the number of connections between them. The following \(m\) lines each contain two integers \(u\) and \(v\) (1-indexed), indicating that switch \(u\) is connected to switch \(v\) (and vice versa).

outputFormat

Output the minimum number of switch presses needed to turn all switches off. If there is no way to turn off all switches, output Change an alarm clock, please! (without the quotes).

sample

4 3
1 2
2 3
3 4

2