Electrical circuit#3529
Andrey is a budding radio enthusiast. Recently, he came across a radio transmitter circuit in a youth science magazine called "Young Inventor" and decided to build it himself. This circuit consists of transistors, some of which are connected by wires. In the magazine's diagram, the transistors are numbered from to . A unique feature of this circuit is that it only functions if the correct voltage is applied to each component — specifically, the -th transistor requires volts.
Andrey eagerly assembled the circuit following the magazine's instructions. However, he wasn't careful enough and soon forgot which voltage should be applied to each transistor. The problem is that while the transistors are numbered in the magazine's diagram, they aren't labeled on the physical circuit he has built.
Now, Andrey needs to figure out which voltage to apply to each transistor to ensure the circuit operates correctly. He doesn't want to test every possible voltage configuration, but only those he deems reasonable. This means he wants to consider only those configurations that satisfy the following conditions:
For each wire in the assembled circuit, if the transistors it connects have voltages volts and volts, then in the magazine's circuit, the transistors numbered and are also connected.
Conversely, if two transistors with voltages volts and volts are not connected by a wire, then in the magazine's circuit, the transistors numbered and are also not connected.
Determine how many configurations Andrey will consider trying.
The first line of the input contains two integers (2 \le n \le 8) and (0 \le m \le n(n-1)/2). Each of the next lines describes a wire and contains two integers and — the numbers of the transistors (as shown in the magazine's circuit) that are connected by this wire (1 \le u, v \le n, u \ne v). No two transistors are connected by more than one wire.
Print the number of configurations Andrey will attempt.
Example 1