TopCoder

User's AC Ratio

88.2% (30/34)

Submission's AC Ratio

31.0% (109/352)

Description

金氏運動公司打算舉辦一場馬拉松比賽,為了締造亮眼的完成比賽時間,金氏運動公司打算選擇性地邀請選手參賽。分析過往的數據資料,金氏運動公司觀察到以下二個現象:
(a) 對於任何一位選手,如果愈多他的朋友參賽,則他就能跑得愈快,所以傾向於找一群選手使得彼此互相認識的情況很多。因為認識是雙向的,如果$P$ 認識$Q$,則$Q$ 認識$P$。所以當我們說$P$ 認識$Q$ 時,等同於表示$P$、$Q$ 兩位互相認識。
(b) 如果參賽的選手當中,存在兩位選手$P$ 和$Q$ 彼此不認識,而且在參賽的選手當中無法找到$t$ 位選手$S_1, S_2,\ldots S_t$ ($t$ 為任意大於0 的整數),使得$P$ 認識$S_1$,$S_1$ 認識$S2$,…,$S_{t-1}$ 認識$S_t$,$S_t$ 認識$Q$,則比賽將會有嚴重的惡性競爭,所以需要避免這樣的狀況。

現在金氏運動公司手上有一份$N$ 位選手的名單以及一份顯示這$N$ 位選手彼此之間是否認識的表單,現在的任務是從這$N$ 位選手找出選手的子集合$S = \{P_1, P_2, \ldots, P_{\lvert S \rvert} \}$,使得$S$ 沒有惡性競爭的狀況,而且讓以下影響因子$F(S)$得到最大化,這影響因子的設計除了讓每位選手都認識夠多的參賽者,也兼顧了不讓參賽人數過少。
$$F(S) = \lvert S \rvert \min\limits_{1\leq i \leq \lvert S \rvert} D_i$$
其中$D_i$ 表示選手$P_i$ 所認識的人當中,有多少人在子集合$S$ 裡面。 在以下這個4 位選手的例子中,選 $S = \{2, 3, 4\}$ 比其他的選法有更高的$F(S)$。

Input Format

每一組測試資料有兩列, 其中第一列有兩個正整數$N$ 和$M (1\leq M \leq \frac{N(N-1)}{2})$,第二列有$M$ 對正整數$X_1 Y_1 X_2 Y_2 \ldots X_M Y_M$,代表選手$X_i$ 認識選手$Y_i $ ($1\leq i \leq M$ 且$1\leq Xi < Yi \leq N$)。

Output Format

對於每組測試資料,輸出最大的$F(S)$。$F(S)$這數字需獨自佔一列。

Sample Input

Sample Input #1
4 5
1 2 2 3 3 4 4 1 2 4

Sample Input #2
4 4
1 2 2 3 3 4 2 4

Sample Input #3
6 6
1 3 1 2 2 3 4 5 5 6 4 6

Sample Output

Sample Output #1
8

Sample Output #2
6

Sample Output #3
6

Hints

本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料中$N \leq 100$,全部解出可獲19 分;
第二子題的測試資料中$N \leq 500$,全部解出可獲38 分;
第三子題的測試資料中$N \leq 5000$,全部解出可獲43 分。

Problem Source

106學年度高級中學資訊學科能力競賽決賽 程式設計試題第五題

Subtasks

No. Testdata Range Score
1 0~9 19
2 10~19 38
3 20~29 43

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 524288 262144 1
1 4000 524288 262144 1
2 4000 524288 262144 1
3 4000 524288 262144 1
4 4000 524288 262144 1
5 4000 524288 262144 1
6 4000 524288 262144 1
7 4000 524288 262144 1
8 4000 524288 262144 1
9 4000 524288 262144 1
10 4000 524288 262144 2
11 4000 524288 262144 2
12 4000 524288 262144 2
13 4000 524288 262144 2
14 4000 524288 262144 2
15 4000 524288 262144 2
16 4000 524288 262144 2
17 4000 524288 262144 2
18 4000 524288 262144 2
19 4000 524288 262144 2
20 4000 524288 262144 3
21 4000 524288 262144 3
22 4000 524288 262144 3
23 4000 524288 262144 3
24 4000 524288 262144 3
25 4000 524288 262144 3
26 4000 524288 262144 3
27 4000 524288 262144 3
28 4000 524288 262144 3
29 4000 524288 262144 3