Названия трех задач взяты из заголовка песни альбома Girls POP Vol.2. Эта серия альбомов просто потрясающая~
На небе есть $n$ звезд, и чтобы обозначить созвездия, люди провели $m$ связей между этими $n$ звездами. Созвездие определяется как непустое подмножество звезд. Плотность созвездия определяется следующим образом: для каждой звезды в созвездии подсчитывается количество связей, соединяющих её с другими звездами внутри этого же созвездия. Плотность созвездия — это минимальное из этих значений среди всех звезд, входящих в данное созвездие.
Найдите созвездие с максимальной плотностью.
Входные данные
Первая строка содержит два целых положительных числа $n$ и $m$, обозначающих количество звезд и количество связей соответственно.
Далее следуют $m$ строк, каждая из которых содержит два целых положительных числа $u$ и $v$, означающих, что между звездой $u$ и звездой $v$ существует связь.
Гарантируется, что между двумя звездами существует не более одной связи, и каждая связь соединяет две различные звезды.
Выходные данные
Выведите одно целое положительное число — максимальную плотность среди всех возможных созвездий.
Примеры
Пример 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
Выходные данные
3
Примечание к примеру 1
Вид созвездия показан на рисунке:
Выбор звезд $1, 2, 3, 4, 5$ позволяет достичь максимальной плотности.
Ограничения
Для $100\%$ данных $n, m \le 10^5$.
| Тест | $n$ | $m$ |
|---|---|---|
| $1,2$ | $\le 3$ | $\le3$ |
| $3,4,5$ | $\le3$ | $\le10^2$ |
| $6,7$ | $\le18$ | $\le10^3$ |
| $8$ | $\le10^3$ | $\le10^5$ |
| $9,10$ | $\le10^5$ | $\le10^5$ |
История
Аскатлан, мне все еще нравится называть ее просто Лан.
В детстве Лан была очень милой, особенно когда смотрела на звезды. Ее глаза были винно-красного цвета, способные очаровать любого.
Сегодня вечером мы снова сидели вместе на крыше. Я держал звездную карту и помогал ей узнавать созвездия одно за другим. «Почему я не вижу этих линий на небе?» «А, это мы нарисовали их на карте, чтобы лучше запомнить очертания каждого созвездия».
«Хе-хе, мне больше всего нравится это созвездие, жаль, что сейчас оно выглядит не очень отчетливо». «Да, мы не всегда можем видеть все звезды, изображенные на этой карте...»
В этот момент я заметил, что она начала задумчиво смотреть в сторону этого созвездия на ночном небе. Мне показалось? Казалось, что звезды этого созвездия постепенно становятся ярче, в то время как остальные звезды мгновенно меркнут.
Она повернула голову, улыбнулась мне и сказала: «Хе-хе, тогда расскажи мне историю этого созвездия».