29153번 - 성게 밭

문제

제주도민 동근이는 집안 대대로 내려오는 가업을 잇기 위해 긴 상경 생활을 마치고 제주도로 돌아왔다. 제주도에서 제일가는 해녀의 아들이었던 동근이는 부모님의 뜻을 따라 해남이 되기로 하였다. 이제 해남으로써 첫발을 내디딘 동근이는 어머니를 따라 옆에서 같이 잠수 연습 겸 채집을 하려고 한다. 지금은 7월에서 8월이고 성게 제철이라 성게가 바다에 굉장히 많다.

성게들은 정점과 방향 없는 간선으로 구성된 그래프로 표현이 될 수 있다.

• 성게는 $T=(V,E)$ 에서 $c \in V, \deg (c)= \lvert V \rvert - 1$을 만족하는 유일한 $c$가 존재하고 $\deg (c) \ge 3$를 만족하는 트리 구조를 가진다.
• 하나의 성게에서 정점 $c$를 성게의 중심, 중심이 아닌 다른 정점들을 성게의 가시라고 부른다.
• 성게 밭은 한 개 이상의 성게를 부분 그래프로 가지는 그래프이다. 성게 밭의 모든 정점과 간선은 적어도 하나의 성게에 속한다.
• 성게 밭에서 한 정점이 성게의 중심이라면, 그 정점은 다른 성게의 중심이나 가시로써 포함되지 않는다. 즉, 성게의 중심인 정점은 정확히 하나의 성게에만 속한다.
• 성게 밭에서 서로 다른 두 성게의 가시는 공유될 수 있으며, 두 성게가 가시 하나 이상을 공유한다면 그 두 성게는 맞닿아 있다고 한다.
• 성게 밭에서 각 성게는 암컷 혹은 수컷이며, 지금 시기는 성게가 제철이기에 성게 밭은 서로 다른 두 암컷이나 두 수컷은 맞닿아 있지 않다.

예시로 다음 그림을 살펴보자. 그림에서 주어진 성게밭은 중심이 1, 7인 성게가 가시 2, 3을 통해 맞닿고 있다. 또한 모든 정점과 간선이 한 개 이상의 성게에 포함되며, 성게의 중심인 정점 1, 7은 정확히 하나의 성게에 속한다.

동근이는 이 성게들을 채집하기 위해 바다로 들어가려고 한다. 하지만 동근이는 잠수 경험이 없었기 때문에 오래 잠수할 수 없어서, 잠수 한 번에 정확히 하나의 성게만 채집할 수 있다. 이때, 성게 하나를 채집하면 맞닿아 있는 성게들의 가시가 부러져 상품성이 떨어지므로, 채집한 성게와 맞닿은 있는 성게들은 더 이상 채집할 수 없다.

구체적으로, 초기에 모든 성게는 채집할 수 있는 상태이다. 잠수를 하여 채집할 수 있는 성게 하나를 채집하면, 그때 채집한 성게와 맞닿아 있는 성게들은 더 이상 채집할 수 없는 상태가 된다. 이때, 동근이는 원하는 횟수만큼 잠수하여 최대한 많은 성게를 채집하려고 한다. 동근이를 위해 최대 몇 개의 성게를 채집할 수 있는지 구해주자.

입력

첫 줄에 성게 밭의 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 15,円 000;$ 1ドル \le M \le 30,円 000)$

둘째 줄부터 $M$개의 줄에 걸쳐 간선의 정보를 나타내는 두 정수 $a_i,ドル $b_i$가 공백으로 구분되어 주어진다. $(1 \leq i \leq M;$ 1ドル \le a_i, b_i \le N;$ $a_i \neq b_i)$

이는 성게 밭의 $a_i$ 번째 정점과 $b_i$ 번째 정점이 방향 없는 간선으로 이어져 있다는 것을 의미한다. 같은 간선은 중복해서 주어지지 않는다.

입력으로는 항상 성게밭 조건에 만족하는 그래프가 들어온다.

출력

동근이가 채집할 수 있는 성게의 최대 개수를 출력한다.

제한

힌트