17493번 - 동아리 홍보하기 서브태스크

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

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

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

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

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

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

• 1 ≤ N ≤ 200,000
• 0 ≤ M ≤ N-1

• N ≤ 8

• 추가 제한 조건은 없다.