정점 선인장의 자기 동형 수

정점 선인장은 다음 조건을 만족하는 연결 무방향 그래프이다.

• 모든 정점은 많아야 하나의 단순 사이클에 포함된다.

단순 사이클은 시작 정점과 끝 정점을 제외하면 어떤 정점도 두 번 이상 나타나지 않는 사이클이다.

정점에 1번부터 N번까지 번호가 매겨진 그래프 G가 주어진다. G의 자기 동형은 G에 간선 i-j가 있을 때마다 G에도 간선 P[i]-P[j]가 존재하도록 하는 순열 P[1], P[2], ..., P[N]이다.

G가 정점 선인장일 때, G의 자기 동형 개수를 $10^9 + 3$으로 나눈 나머지를 구하라.

첫째 줄에 그래프 G의 정점의 개수 N과 간선의 개수 M이 주어진다. N은 200보다 작거나 같은 자연수이고, M은 0보다 크거나 같은 정수이다.

다음 M개의 줄에는 간선의 정보가 주어진다. 각 줄에는 하나의 간선을 나타내는 두 정수가 공백으로 구분되어 주어진다. 입력으로 주어지는 간선은 중복되지 않으며, 모든 정점 쌍은 많아야 한 개의 간선으로 연결된다. 그래프 G는 항상 정점 선인장이다.

첫째 줄에 정답을 출력한다.