Cactus Graph Automorphisms

A vertex cactus is a connected undirected graph with the following property.

• Every vertex belongs to at most one simple cycle.

A simple cycle is a cycle in which no vertex appears more than once, except that the first and last vertices are the same.

You are given a graph G whose vertices are numbered from 1 to N. An automorphism of G is a permutation P[1], P[2], ..., P[N] such that whenever G has an edge i-j, G also has the edge P[i]-P[j].

Given that G is a vertex cactus, compute the number of automorphisms of G modulo $10^9 + 3$.

The first line contains two integers N and M, the number of vertices and edges of G. N is a positive integer not greater than 200, and M is a nonnegative integer.

Each of the next M lines contains two space-separated integers describing one edge. The input contains no duplicate edges, and each pair of vertices is connected by at most one edge. The graph G is always a vertex cactus.

Output the answer on the first line.