The titles of these three problems are taken from a song title on the album Girls POP Vol.2. This series of albums is wonderful!
There are $n$ stars in the sky. To identify constellations, people have drawn $m$ links between these $n$ stars. A constellation is defined as a non-empty set of stars. The density of a constellation is determined by finding a star within it that has the minimum number of links to other stars in the same constellation; this minimum number is the density of the constellation.
Please find a constellation with the maximum possible density.
Input
The first line contains two positive integers $n$ and $m$, representing the number of stars and the number of links, respectively.
The next $m$ lines each contain two positive integers $u$ and $v$, indicating a link between star $u$ and star $v$.
It is guaranteed that there is at most one link between any two stars, and each link connects two distinct stars.
Output
Output a single positive integer representing the maximum density among all possible constellations.
Examples
Input 1
8 13 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 7 3 5 3 7 4 5 4 8 5 6
Output 1
3
Note 1
The constellation structure is shown in the figure below:
Retaining stars 1, 2, 3, 4, and 5 achieves the maximum density.
Constraints
For $100\%$ of the data, $n, m \le 10^5$.
| Test Case | $n$ | $m$ |
|---|---|---|
| $1,2$ | $\le 3$ | $\le 3$ |
| $3,4,5$ | $\le 3$ | $\le 10^2$ |
| $6,7$ | $\le 18$ | $\le 10^3$ |
| $8$ | $\le 10^3$ | $\le 10^5$ |
| $9,10$ | $\le 10^5$ | $\le 10^5$ |
Story
Athkatla—I still prefer to call her Lan.
Lan was very cute when she was a child, especially when she looked at the stars. Her eyes were wine-red, enough to intoxicate anyone who looked into them.
Tonight, we are sitting on the roof together again. I am holding a star map, helping her identify one constellation after another. "Why don't I see these lines in the sky?" "Ah, those are lines we drew on the star map to help us better remember the shape of each constellation."
"Hehe, this is my favorite constellation, but it doesn't look very obvious right now." "Yeah, we can't always see all the stars on this map either..."
At that moment, I noticed her staring intently in the direction of that constellation in the night sky. Was it my imagination? It seemed as if the stars of that constellation were gradually becoming brighter, while the other stars immediately appeared dim in comparison.
She turned her head, smiled at me, and said, "Hehe, then tell me the story of this constellation."