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

문제

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

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

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

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

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

그래프 G의 연결 요소란 정점의 집합인데, 집합 내의 모든 쌍의 정점이 경로로 연결되어 있고, 집합 밖의 정점과 집합 내의 정점이 연결되어 있지 않을 때이다.

입력

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

출력

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

예제 입력 1

3 3
1 2
1 3
2 3

예제 출력 1

1

예제 입력 2

10 0

예제 출력 2

10

예제 입력 3

5 3
1 2
3 4
4 5

예제 출력 3

2

예제 입력 4

17 19
1 2
2 3
3 4
4 5
5 3
1 3
6 7
7 8
6 8
8 9
9 10
10 11
11 9
12 13
14 15
15 16
16 17
14 17
14 16

예제 출력 4

2

출처