A delivery network has n locations (numbered 1 to n) connected by m two-way roads. A route is a sequence that visits every one of the n locations exactly once, moving from one location to the next only along a direct road. Two routes are different if the sequence of locations differs in any position — in particular, a route and the same route driven in reverse are counted as two different routes (unless n = 1).
Count the total number of such routes.
Input format
Line 1: two integers n and m.
Next m lines: two integers u v (1-indexed) — a two-way road between location u and location v.
Output format
A single integer: the number of routes that visit every location exactly once using only direct roads.
Constraints
- 1 ≤ n ≤ 8
- 0 ≤ m ≤ n*(n-1)/2, with no self-loops and no duplicate roads