Cactus Graph Automorphisms

Time limit2sMemory limit128 MB

Summary

Count automorphisms modulo 1e9+3 of a given vertex cactus graph with up to 200 vertices.

Level: Hard9 of 10
Topics: Tree, Combinatorics, Graph, DFS
Solved: No attempts yet

Problem

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$ .

Input

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

Output the answer on the first line.

Examples4

Example 1
Input
```
4 3
1 2
1 3
1 4
```
Expected output
```
6
```
Example 2
Input
```
4 4
1 2
2 3
3 4
4 1
```
Expected output
```
8
```
Example 3
Input
```
6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4
```
Expected output
```
8
```
Example 4
Input
```
1 0
```
Expected output
```
1
```