P10942 GF and the Cat’s Toy

Student GF and a cat got a special toy. The toy consists of $n$ metal rings (numbered $1 \sim n$) and $m$ ropes. Each rope connects two different metal rings, and all ropes have the same length. GF picks up ring $L$ with his left hand, and the cat picks up ring $R\ (L \ne R)$ with its right hand (or paw). Then they pull as hard as possible in opposite directions. GF wants to choose suitable $L$ and $R$ so that the number of ropes that become taut is as large as possible. Note: If, as in the sample, $1 \to 2 \to 4 \to 3 \to 5 \to 6 \to 1$ forms a cycle, we consider that when pulling $1$ and $3$, only one side can be made taut ($1 \to 2 \to 4 \to 3$ or $3 \to 5 \to 6 \to 1$), and it does not count as making all of them taut. In plain words, when there are multiple connection ways between two rings with the same number of ropes, only one of these ways is counted as being made taut, not all of them.

The first line contains two positive integers $n, m$ ($n \le 100$). The next $m$ lines each contain two positive integers $a, b$, meaning there is a rope connecting $a$ and $b$.

Only one integer, representing the maximum number of ropes that can be made taut.

Translated by ChatGPT 5