この3問のタイトルは、アルバム Girls POP Vol.2 に収録されている曲名から取ったものです。このシリーズのアルバムはどれも素晴らしいですよ〜。
空には $n$ 個の星があり、星座を識別するために、これらの $n$ 個の星の間に $m$ 本の線が引かれています。星座とは、星からなる空ではない集合と定義されます。ある星座の「密集度」とは、その星座内の星のうち、星座内の他の星と結ばれている線の数が最小である星を選んだとき、その線の数のことを指します。
密集度が最大となる星座の密集度を求めてください。
入力
1行目に2つの正整数 $n, m$ が与えられ、それぞれ星の数と線の数を表します。
続く $m$ 行には、それぞれ2つの正整数 $u, v$ が与えられ、星 $u$ と星 $v$ の間に線があることを表します。
2つの星の間に引かれる線は最大で1本であり、各線は異なる2つの星を結ぶことが保証されています。
出力
密集度が最大となる星座の密集度を正整数で出力してください。
入出力例
入力 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
出力 1
3
注記 1
星座の様子は図の通りです：
星 $1, 2, 3, 4, 5$ を残すことで、最大の密集度を達成できます。
制約
$100\%$ のデータにおいて、$n, m \le 10^5$ である。
| テストケース | $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$ |
ストーリー
アスカトラン、私はやはり彼女を直接「ラン」と呼びたい。
幼い頃のランはとても可愛らしく、特に星を見上げているときはそうだった。彼女の瞳はワインレッドで、誰もがその中に酔いしれてしまうほどだった。
今夜、私たちは再び一緒に屋根の上に座っている。私は星図を手に、彼女に星座を一つずつ教えていた。「どうして空にはこれらの線が見えないの？」「ああ、それは私たちが星座の形を覚えやすくするために、星図の上に描いたものなんだよ」
「へへっ、私はこの星座が一番好き。でも、今はあまりはっきり見えないね」「そうだね、星図にある星をいつもすべて見られるわけじゃないからね……」
その時、彼女がその星座のある空の方向をぼんやりと見つめ始めたことに気づいた。気のせいだろうか？ まるでその星座の星々が次第に明るさを増し、他の星たちがすぐに色あせて見えるようになった。
彼女は振り返り、私に向かってにっこりと笑って言った。「ねえ、それじゃあ私にこの星座の物語を話してよ」