TopCoder

Thumb 343jksfld
ltf0501
願與最重要之人能再次相會。

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

84.6% (22/26)

Description

  X 班級共有 n 個學生,為了方便說明,我們將每位學生以非負整數{0, 1, 2, …, (n–1)}來表示。每位學生在學校網站上有一個自己的部落格可以發表資訊,也可以在獲得別的同學的關注授權後閱讀其部落格,已知 n 個學生之間共存在有 m 個閱讀授權,我們可以用一個有向圖來表示學生間部落格的授權關係:以非負整數點代表學生的編號,以有向邊 (u, v) 代表學生 v 同意學生 u 閱讀其部落格。若一個有向圖中,圖上的任兩點都可以透過一連串同方向的有向邊相連,我們稱呼此圖為一個半連通圖(semi-connected graph)。
  在校慶活動上,每位學生都將獲得一個抽獎號碼,同班同學中,若有兩人得到相同號碼即可獲得大獎,學生小明想了一個對獎方法,每個人把抽到的號碼貼在自己的部落格上,並將所有關注對象的部落格內容都貼到自己的部落格上,這樣每個人都可以由部落格內容看出是不是有人的號碼跟自己的一樣。
  如此一來,如果班上同學間的部落格授權關係圖是一個半連結圖,則小明的方法就可以讓得獎的兩人其中之一找到另一個得獎人。但很可惜地,對於一個尋常的班級來說,部落格授權關係是一個半連結圖的可能性頗低。根據學生間的授權關係圖,你能不能幫忙小明找出這個班級當中人數最多的一群同學,使得這群同學間的授權關係圖為半連結圖呢?
  以下圖為例,這是某班級的部落格連結(授權閱讀)關係圖,此圖不是一個半連結圖 (semiconnected graph):若 2 號及 3 號學生抽中同一號碼,則他們沒辦法透過部落格找到彼此。
  若我們考慮子集合 {0, 1, 2},則這三位同學之間的授權關係形成一個半連結圖。

Input Format

每組測資的第一行有 2 個整數,代表學生人數$1\leq n $與部落格閱讀授權數$0\leq m\leq n(n-1)$,兩個數字以空白隔開。第二行起接下來$ m $行,每行兩個整數代表$ m $條閱讀授權 (任兩個數字以空白隔開):第一個數字代表要求授權的學生、第二個數字代表同意授權的學生。輸入中要求授權的學生與同意授權的學生配對不會重複出現。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 12, m\leq 50$ 17
2 (0~9) $n\leq 30, m\leq 200$ 8
3 (0~14) $n\leq 100, m\leq 9900$ 26
4 (0~19) $n\leq 3000, m\leq 10^ 6$ 22
5 (0~24) $n\leq 10^ 6, m\leq 10^ 6$ 27

Output Format

針對所輸入的資料,輸出一個整數 k,使得小明能夠從中找到至多 k 個同學,他們的授權關係圖為一個半連通圖(semi-connected graph)。

Sample Input

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

Sample Output

#Sample Output 1
3
#Sample Output 2
5
#Sample Output 3
2

Hints

Problem Source

題目取自2017 TOI選訓第四次模擬考pC
Problem set by Yihda Yol

Subtasks

For Testdata: 0 ~ 4, Score: 17
For Testdata: 0 ~ 9, Score: 8
For Testdata: 0 ~ 14, Score: 26
For Testdata: 0 ~ 19, Score: 22
For Testdata: 0 ~ 24, Score: 27
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 65536
1 1000 262144 65536
2 1000 262144 65536
3 1000 262144 65536
4 1000 262144 65536
5 1000 262144 65536
6 1000 262144 65536
7 1000 262144 65536
8 1000 262144 65536
9 1000 262144 65536
10 1000 262144 65536
11 1000 262144 65536
12 1000 262144 65536
13 1000 262144 65536
14 1000 262144 65536
15 1800 262144 65536
16 1800 262144 65536
17 1800 262144 65536
18 1800 262144 65536
19 1800 262144 65536
20 1800 262144 65536
21 1800 262144 65536
22 1800 262144 65536
23 1800 262144 65536
24 1800 262144 65536