시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 100 9 8 42.105%

문제

건덕이는 건국대학교의 프로그래밍 동아리 알프스(ALPS)를 홍보하기 위해 전봇대에 전단지를 붙이고 있다. 하지만 전단지를 붙이는 것도 보통 일이 아니라서, 최소한의 전단지로 최고의 홍보 효과를 내고싶어한다.

전봇대와 전봇대 사이는 연결된 길로만 다닐 수 있다. 전단지는 전봇대에 붙이고, 전단지를 붙인 전봇대와 이웃한 전봇대까지 홍보 효과가 나타나며, 어떤 전봇대에서 출발하여 다른 길을 통해 다시 그 전봇대로 돌아올 수 있는 경로는 없다. 건덕이는 새이기 때문에, 길과 상관없이 날아서 다른 전봇대에 전단지를 붙일 수 있다.

두 전봇대 사이에 연결된 길들이 주어질 때, 건덕이가 붙여야 하는 최소 전단지의 개수를 구해 보자.

입력

전봇대의 수 N, 길의 개수 M이 공백으로 구분돼 주어진다.

이어지는 M개의 줄에는 두 자연수 A, B가 주어진다. A번째 전봇대와 B번째 전봇대 사이에 길이 있음을 의미한다. (전봇대는 1부터 N까지 번호매김된다)

출력

모든 전봇대에서 홍보효과를 누릴 수 있도록 하는 데 필요한 전단지의 최소 개수를 출력한다.

제한

  • 1 ≤ ≤ 200,000
  • 0 ≤ MN-1

서브태스크 1 (60점)

  • N ≤ 8

서브태스크 2 (40점)

  • 추가 제한 조건은 없다.

예제 입력 1

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

예제 출력 1

3


1, 4, 7번 전봇대에 전단지를 붙이면, 모든 곳에서 전단지를 볼 수 있다.

예제 입력 2

5 0

예제 출력 2

5

채점

  • 예제는 채점하지 않는다.