原題來自：ZJOI 2007

一個(gè)有向圖 G=(V,E) 稱為半連通的 (Semi-Connected)，如果滿足：?u,v∈V，滿足 u→v或 v→u，即對(duì)于圖中任意兩點(diǎn) u,v，存在一條 u 到 v 的有向路徑或者從 v 到 u 的有向路徑。

若 G'=(V',E') 滿足，E' 是 E 中所有和V' 有關(guān)的邊，則稱G' 是 G 的一個(gè)導(dǎo)出子圖。若 G' 是 G 的導(dǎo)出子圖，且 G' 半連通，則稱 G' 為 G 的半連通子圖。若G' 是 G 所有半連通子圖中包含節(jié)點(diǎn)數(shù)最多的，則稱 G' 是 G 的最大半連通子圖。

給定一個(gè)有向圖 G，請(qǐng)求出 G 的最大半連通子圖擁有的節(jié)點(diǎn)數(shù) K，以及不同的最大半連通子圖的數(shù)目 C。由于 C 可能比較大，僅要求輸出 C 對(duì) X 的余數(shù)。

第一行包含三個(gè)整數(shù) N,M,X。N,M 分別表示圖 G 的點(diǎn)數(shù)與邊數(shù)，X 的意義如上文所述；

接下來 M 行，每行兩個(gè)正整數(shù) a,b，表示一條有向邊 (a,b)。

圖中的每個(gè)點(diǎn)將編號(hào)為 1,2,3,?,N，保證輸入中同一個(gè) (a,b)不會(huì)出現(xiàn)兩次。

應(yīng)包含兩行。第一行包含一個(gè)整數(shù) K，第二行包含整數(shù)C modX。

對(duì)于 20% 的數(shù)據(jù)，N≤18；

對(duì)于 60% 的數(shù)據(jù)，N≤10⁴ ；

對(duì)于 100% 的數(shù)據(jù)，1≤N≤10⁵,1≤M≤10⁶,X≤10⁸ 。

信息學(xué)一本通 圖論