성게 밭

제주도민 동근이는 집안 대대로 내려오는 가업을 잇기 위해 긴 상경 생활을 마치고 제주도로 돌아왔다. 제주도에서 제일가는 해녀의 아들인 동근이는 부모님의 뜻을 따라 해남이 되기로 했다. 해남이 된 동근이는 어머니를 따라 옆에서 잠수 연습을 겸해 채집을 하려고 한다. 지금은 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 \le i \le M$, $1 \le a_i, b_i \le N$, $a_i \neq b_i$)

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

입력은 항상 성게 밭 조건을 만족하는 그래프다.

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