Description

Studies show that this infectious disease has two very special properties.

First, its transmission routes form a tree. A person $X$ can only be infected by a specific person $Y$. As long as $Y$ does not get sick, or the transmission route between $X$ and $Y$ (i.e., $XY$) is cut, $X$ will not get sick.

Second, the disease spreads periodically. Within one transmission period, it infects only one generation of patients, and does not spread further to the next generation in that period.

These properties greatly reduce the pressure on Penglai’s disease control efforts, and they have already obtained a potential transmission map (a tree) for part of the susceptible population. However, the problem is not over. Due to limited manpower and technology, during one transmission period they can cut only one transmission route. Any remaining, uncontrolled routes will cause more susceptible people to be infected (that is, people who are connected to the currently infected by a transmission route that has not been cut). When it becomes impossible for any healthy person to be infected, the disease stops spreading. Therefore, Penglai’s CDC must decide an order in which to cut transmission routes so that as few people as possible become infected.

Your program must, for the given tree, find an appropriate cutting order.

Input Format

The first line contains two integers $n$ and $p$.
The next $p$ lines each contain two integers $i$ and $j$, indicating there is an edge between nodes $i$ and $j$ (that is, there is a transmission route between person $i$ and person $j$). Node $1$ is already infected. The graph is a tree, so $p = n - 1$.

Output Format

One line: the total number of people who get infected.

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

3

Hint

Constraints: For $100\%$ of the testdata, $1 \leq n \leq 300$.

Source: NOIP 2003 Senior, Problem 4.

Translated by ChatGPT 5