시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB287630.000%

문제

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

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

단순 사이클이란 사이클 중에서 시작과 끝을 제외하고 각 정점들이 많아야 한 번씩 나타날 때이다.

다음 그림은 정점 선인장이다.

정점의 번호가 1번부터 N번까지 매겨져 있는 그래프 G가 주어진다. 이것의 Automorphisms은 간선 i-j가 있을 때, 간선 P[i]-P[j]가 항상 존재한다는 조건을 만족하는 순열 P[1], P[2], ..., P[N]이다.

정점 선인장인 그래프 G의 정점의 개수 N이 주어진다. 정점은 1번부터 N번까지 번호가 매겨져 있다. 그래프의 간선이 어떻게 연결되어 있는지가 주어질 때, 주어진 정점 선인장의 Automorphisms의 개수를 109+3으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 그래프 G의 정점의 개수 N과 간선의 개수 M이 주어진다. N은 200보다 작거나 같은 자연수이고, M은 0보다 크거나 같은 정수이다. 다음 M개의 줄에 간선의 정보가 주어진다. 간선의 정보는 공백으로 구분되어 있는 한 쌍의 정수이다. 입력으로 주어지는 간선은 중복되지 않으며, 모든 쌍의 정점은 많아야 한 개의 간선으로 연결될 것이다. 그리고, 그래프 G는 항상 정점 선인장이다.

출력

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

예제 입력 1

4 3
1 2
1 3
1 4

예제 출력 1

6

예제 입력 2

4 4
1 2
2 3
3 4
4 1

예제 출력 2

8

예제 입력 3

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

예제 출력 3

8

예제 입력 4

1 0

예제 출력 4

1

출처