TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (4/4)

Tags

Description

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

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

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

經過不眠不休的分析以及觀察,殿壬終於找出那個組織的內部通訊圖等相關資訊:組織裡面總共有 $N + 1$ 個人(組織內部的人以 $0$ 到 $N$ 編號),並且有 $M$ 組單向的通訊方式,通訊方式以 $1$ 到 $M$ 編號,第 $i$ 個通訊方式為:編號 $a_i$ 的人可以跟編號 $b_i$ 的人直接聯繫。如果編號為 $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$ 裡面,並且 $E$ 跟 $F$ 可以「間接聯繫」 或「直接聯繫」

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

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

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

Input Format

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

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

第三行的格式為 $(a_1 \ b_1), (a_2 \ b_2), ...... (a_{M-1} \ b_{M-1}), (a_M \ b_M)$ ,裡面的變數意義都在題目敘述中提過了。

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

  • $0 \le N \le 2 \times 10^ 5$
  • $0 \le M \le 2 \times 10^ 5$
  • $a_i \ne b_i$
  • $0 \le a_i, b_i \le N$

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