Electricity

A company supplies electricity through several power plants, and each plant serves the small area around it. Because one area can run short of power while another has a large surplus, the company has decided to link the networks of some plants together.

At least in the first stage, not every plant has to belong to a single network. On the other hand, building redundant links at critical points can be worthwhile, so the combined network may contain cycles.

One criterion for evaluating a proposed layout is reliability. We assume the worst event is a malfunction at one of the joining points located at a power plant, which may split the network into several parts. Each part can keep working on its own, but each must then cope with its own shortages, so it is important to know how badly a single failure can fragment the network.

Write a program that, given a description of the network, determines the maximum number of separate parts the network may break into after one joining point is removed. The removed joining point itself is not counted.

The input contains several instances.

The first line of each instance has two integers $P$ and $C$ separated by a space, where $1 \le P \le 10000$ and $C \ge 0$. $P$ is the number of power plants, numbered from $0$ to $P-1$, and $C$ is the number of connections.

Each of the next $C$ lines contains two integers $p_1$ and $p_2$ with $0 \le p_1, p_2 < P$, meaning that plants $p_1$ and $p_2$ are connected. Every connection is listed exactly once, and there is at most one connection between any pair of plants.

Instances follow one another with no separator. The input ends with a line containing two zeros.

For each instance, print one line with a single integer: the maximum number of connected parts the network can be broken into by removing one joining point at a power plant.