殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲、兩歲又四個月時開始研究「匹配問題」、兩歲又八個月時開始研究「獨立集問題」、三歲時開始研究蝴蝶、六歲時開始發大財,而現在要講的,是殿壬七歲大時的故事。
殿壬在六歲時,發過大財(當上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$ 間接聯繫。
上述的資訊殿壬都收集到了,接下來,他需要好好的分析以下三件事情:這個組織有多少個「群體」、這個組織的「領導者」、以及這個組織人數最大的「群體」。因為資料量太大了,殿壬難以用肉眼處理,於是他就把這個任務交給你了~
第一行包含一個整數 $N$ ,意義如題目敘述所述。
第二行包含一個整數 $M$ ,意義如題目敘述所述。
第三行的格式為 $(a_1 \ b_1), (a_2 \ b_2), ...... (a_{M-1} \ b_{M-1}), (a_M \ b_M)$ ,裡面的變數意義都在題目敘述中提過了。
建議參考範例輸入以獲得更詳細的資訊。
輸出包含三行。
第一行包含一個整數,代表組織有多少個「群體」。
第二行要輸出跟「領導者」有關的資訊。如果組織不存在領導者,請輸出 No Leader
。否則請由小到大輸出所有屬於「領導者」(包括群體、個體)的人的編號。
第三行要輸出跟人數最大的「群體」有關的資訊。如果整個組織不存在群體的話,請輸出 None
。否則定義 $S$ 是人數最大的群體的人數,請由小到大輸出所有屬於「人數為 $S$ 的群體」的人的編號。
No. | Testdata Range | Score |
---|---|---|
1 | 0~34 | 1 |