TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (4/4)

Tags

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲、兩歲又四個月時開始研究「匹配問題」、兩歲又八個月時開始研究「獨立集問題」、三歲時開始研究蝴蝶、六歲時開始發大財,而現在要講的,是殿壬七歲大時的故事。

殿壬在六歲時,發過大財(當上IOICamp市的市長)後,就開始在探索人生的意義:「我現在都有那麼多錢,從零開始的異世界生活等熱銷動漫的週邊商品都買的差不多了,剩下的錢要做什麼呢?」想著想著,突然有個人從殿壬後面走過來,拿著泡過昏迷藥水的毛巾,捂住殿壬的口鼻。殿壬因此昏倒了。

當殿壬再次醒來之後,發現他的錢財通通不見了,而且,他最心愛的我妻由乃抱枕也被偷走了!殿壬心中嚥不下這口氣。於是,七歲的殿壬決定要當上偵探,來破解偷走他心愛的我妻由乃抱枕的組織。

經過不眠不休的分析以及觀察,殿壬終於找出那個組織的內部通訊圖等相關資訊:組織裡面總共有 N+1 個人(組織內部的人以 0N 編號),並且有 M 組單向的通訊方式,通訊方式以 1M 編號,第 i 個通訊方式為:編號 ai 的人可以跟編號 bi 的人直接聯繫。如果編號為 x 的人可以直接聯繫編號 y 的人,編號 y 的人可以直接聯繫編號 z 的人,在組織內部,編號 x 的人視為可以跟編號為 z 的人間接聯繫。如果 u 可以跟 v 直接或間接聯繫,v 可以跟 w 直接或間接聯繫,在組織內部, u 視為可以跟 w 間接聯繫。上述定義的 u,v,w ,可以是人,也可以是群體、個體(個體、群體的定義會在下面提到)。

組織內部還有定義「群體」:一個群體是由複數個人所構成,並且這些人都可以彼此互相直接聯繫或間接聯繫!組織內部也有定義「個體」:如果一個人他沒有辦法存在任何「群體」中,那這個人就是獨自的「個體」。

兩個群體或個體 C,D 若能「間接聯繫」,代表存在兩個人 E,F ,使得 E 在 群體 C 或個體 C 裡面、F 存在群體 D 或個體 D 裡面,並且 EF 可以「間接聯繫」 或「直接聯繫」

「群體」跟「個體」有個很重要的性質:如果群體或個體 G 可以跟群體或個體 H 間接聯繫,則 HG 不能間接聯繫!

有了這些資訊後,殿壬還發現,這些組織還存在著「領導者」。「領導者」可以是一個群體、或者是一個個體。如果群體或個體 O 是「領導者」,代表存在一個群體或個體 P ,使得 O 可以跟 P 間接聯繫,並且不存在一個群體或個體 Q ,使得 Q 可以跟 O 間接聯繫。

上述的資訊殿壬都收集到了,接下來,他需要好好的分析以下三件事情:這個組織有多少個「群體」、這個組織的「領導者」、以及這個組織人數最大的「群體」。因為資料量太大了,殿壬難以用肉眼處理,於是他就把這個任務交給你了~

Input Format

第一行包含一個整數 N ,意義如題目敘述所述。

第二行包含一個整數 M ,意義如題目敘述所述。

第三行的格式為 (a1 b1),(a2 b2),......(aM1 bM1),(aM bM) ,裡面的變數意義都在題目敘述中提過了。

建議參考範例輸入以獲得更詳細的資訊。

  • 0N2×105
  • 0M2×105
  • aibi
  • 0ai,biN

Output Format

輸出包含三行。

第一行包含一個整數,代表組織有多少個「群體」。

第二行要輸出跟「領導者」有關的資訊。如果組織不存在領導者,請輸出 No Leader 。否則請由小到大輸出所有屬於「領導者」(包括群體、個體)的人的編號。

第三行要輸出跟人數最大的「群體」有關的資訊。如果整個組織不存在群體的話,請輸出 None 。否則定義 S 是人數最大的群體的人數,請由小到大輸出所有屬於「人數為 S 的群體」的人的編號。

Sample Input 1

13
20
(1 2), (2 3), (3 1), (4 1), (4 11), (4 8), (4 5), (5 6), (6 7), (7 5), (8 9), (9 10), (10 8), (11 12), (12 13), (13 11), (1 7), (2 12), (6 9), (13 10)

Sample Output 1

4
4
1 2 3 5 6 7 8 9 10 11 12 13

Sample Input 2

16
24
(1 2), (2 3), (3 1), (4 5), (5 6), (6 7), (7 4), (8 9), (9 10), (10 8), (11 12), (12 13), (13 11), (14 15), (15 16), (16 14), (1 4), (9 5), (7 11), (14 6), (2 8), (3 12), (15 10), (16 13)

Sample Output 2

5
1 2 3 14 15 16
4 5 6 7

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~34 1

Testdata and Limits

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