Nazwy trzech zadań pochodzą z tytułu piosenki z albumu Girls POP Vol.2. Cała ta seria albumów jest niezwykle przyjemna w odbiorze~
Na niebie znajduje się $n$ gwiazd, a ludzie, aby wyznaczyć gwiazdozbiory, narysowali $m$ połączeń między nimi. Gwiazdozbiór definiuje się jako niepusty zbiór gwiazd. Gęstość gwiazdozbioru wyznacza się poprzez znalezienie takiej gwiazdy wewnątrz niego, która ma najmniejszą liczbę połączeń z pozostałymi gwiazdami w tym samym gwiazdozbiorze; ta liczba połączeń jest gęstością gwiazdozbioru.
Znajdź gwiazdozbiór, którego gęstość jest największa.
Wejście
W pierwszej linii znajdują się dwie dodatnie liczby całkowite $n$ oraz $m$, oznaczające odpowiednio liczbę gwiazd i liczbę połączeń.
W kolejnych $m$ liniach znajdują się dwie dodatnie liczby całkowite $u$ oraz $v$, oznaczające, że istnieje połączenie między gwiazdą $u$ a gwiazdą $v$.
Gwarantuje się, że między dwiema gwiazdami istnieje co najwyżej jedno połączenie oraz że każde połączenie łączy dwie różne gwiazdy.
Wyjście
Wypisz jedną dodatnią liczbę całkowitą, oznaczającą maksymalną gęstość gwiazdozbioru.
Przykład
Przykład 1 Wejście
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
Przykład 1 Wyjście
3
Wyjaśnienie
Wygląd gwiazdozbioru przedstawiono na rysunku:
Zachowanie gwiazd $1, 2, 3, 4, 5$ pozwala osiągnąć maksymalną gęstość.
Ograniczenia
Dla $100\%$ danych wejściowych: $n, m \le 10^5$.
| Test | $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$ |
Historia
Athkatla, wciąż wolę nazywać ją po prostu Lan.
Jako dziecko Lan była niezwykle urocza, zwłaszcza gdy patrzyła w gwiazdy. Jej oczy miały kolor czerwonego wina, w którym każdy mógłby utonąć.
Dziś wieczorem znów siedzimy razem na dachu. Trzymam mapę nieba i pomagam jej rozpoznawać kolejne gwiazdozbiory. „Dlaczego nie widzę tych wszystkich linii na niebie?” „Ach, to tylko linie, które rysujemy na mapach, aby łatwiej było zapamiętać kształt każdego gwiazdozbioru”.
„Hehe, najbardziej lubię ten gwiazdozbiór, choć szkoda, że teraz nie wygląda zbyt wyraźnie”. „Tak, nie zawsze możemy zobaczyć wszystkie gwiazdy z tej mapy...”
W tym momencie zauważyłem, że zaczęła w zamyśleniu wpatrywać się w kierunek, w którym ten gwiazdozbiór znajduje się na niebie. Czy to tylko moje złudzenie? Wydawało się, że gwiazdy tego gwiazdozbioru stają się coraz jaśniejsze, podczas gdy inne gwiazdy natychmiast przygasły.
Odwróciła głowę, uśmiechnęła się do mnie i powiedziała: „Hehe, opowiedz mi więc historię tego gwiazdozbioru”.