Graph Automorphisms

A graph automorphism of an undirected graph \(G=(V,E)\) is a bijection \(m: V \to V\) such that for every edge \(\{u,v\} \in E\) we have \(\{m(u), m(v)\} \in E\). In other words, the structure of the graph is preserved under the mapping. Every graph has at least one automorphism (the identity mapping) and can have up to \(n!\) automorphisms for a graph on \(n\) vertices.

In this problem, you are given a cactus graph, i.e. a connected undirected graph in which every edge belongs to at most one simple cycle (a generalization of a tree where some cycles are allowed). Your task is to compute the total number of automorphisms of the given graph and output the answer as a prime factorization in the form \[ \prod_{i=1}^{k} p_i^{q_i} \] where the \(p_i\) are prime numbers in ascending order. Note that if the number of automorphisms equals 1, simply output 1.

Note: Since some graphs are very small (\(n \le 8\)), you may use brute force techniques to test all permutations of vertices.

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(1 \le n \le 8\)), where \(n\) is the number of vertices and \(m\) is the number of edges.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\) and \(u \neq v\)) representing an undirected edge between vertices \(u\) and \(v\). It is guaranteed that the graph is a cactus.

outputFormat

Output the total number of automorphisms of the graph as a prime factorization. For example, if the number equals 6 you should output "2^1 * 3^1". If the number is 1, output "1".

sample

1 0

1