Electrical circuit
Andrey is a budding radio enthusiast. Recently, he came across a radio transmitter circuit in the magazine "Young Radio Technician" and decided to build it himself. This circuit consists of n transistors, some of which are connected by wires. In the magazine's diagram, the transistors are numbered from 1 to n. A unique feature of this circuit is that it only functions if the correct voltage is applied to each component — specifically, the i-th transistor requires i 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 p volts and q volts, then in the magazine's circuit, the transistors numbered p and q are also connected.
Conversely, if two transistors with voltages p volts and q volts are not connected by a wire, then in the magazine's circuit, the transistors numbered p and q are also not connected.
Determine how many configurations Andrey will consider trying.
Input
The first line of the input contains two integers n (2 ≤ n ≤ 8) and m (0 ≤ m ≤ n(n−1)/2). Each of the next m lines describes a wire and contains two integers u and v — the numbers of the transistors (as shown in the magazine's circuit) that are connected by this wire (1 ≤ u, v ≤ n, u ≠ v). No two transistors are connected by more than one wire.
Output
Print the number of configurations Andrey will attempt.