TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

84.6% (77/91)

Submission's AC Ratio

32.0% (133/416)

Tags

Description

你知道八卦嗎?

八卦是中國古代的基本哲學概念,來源有二:

一是中國古代的陰陽學說,所謂「無極生有極,有極是太極,太極生兩儀(即陰陽),兩儀生四象(即少陽,太陽,少陰,太陰),四象演八卦,八八六十四卦」,此為伏羲八卦,也叫先天八卦;

一是周文王的乾坤學說,他認為先有天地,天地相交而生成萬物,天即乾,地即坤,八卦其餘六卦皆為其子女:震為長男,坎為中男,艮為少男;巽為長女,離為中女,兌為少女,是為文王八卦,又稱後天八卦。

八卦符號通常與太極圖搭配出現,代表中國傳統信仰(儒,道)的終極真理——「道」。

「八卦」一詞在現代流行語中,特別是在娛樂新聞中被用作於謠言、緋聞等小道消息代稱。既可做名詞(如「一則八卦」),也可做形容詞(如「八卦消息」、「八卦新聞」)甚至動詞(如「八卦一下某人」,意思即談論某人的小道消息)。

而八卦的新用據說源自於香港。當時有一小道消息雜誌為了提升銷量,而仿效英國成人雜誌在刊物中加入裸女圖片,但又顧慮當時社會風氣可能無法接受,故以八卦圖代替馬賽克遮掩圖中的重點部位。

之後,八卦雜誌遂成為該類雜誌的代稱,而「八卦」一詞也增添了新意涵。

而在這個人人八卦的時代,你發明了一個八卦傳播系統,可以強制把一些八卦灌輸到一個人的腦海中。

基於每個人愛八卦的特性,有些人會將所知的八卦告訴一些好朋友,而好朋友又會將八卦告訴他們的好朋友....

但是,每使用一次八卦傳播機會耗費大量的電力,在這個節能減碳的時代,你希望使用越少次越好。

Input Format

本題只有一組測試資料:

第一行有兩個數字 n, m,代表這組八卦共要讓 n 個人知道,並在這 n 個人當中,有 m 條八卦傳遞路徑
(n, m <= 100,000)

接下來有 m 行,每行有兩個數字 a, b,代表當 a 知道八卦之後,就會跟 b 八卦一下。

Output Format

請對於每筆資料輸出一行,每行有一個數字 k ,代表 最少要使用幾次八卦傳播系統才能人這 n 個人都知道八卦。

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

Hints

對於範例測資

我們只需要對 1 灌輸八卦

1 就會把八卦傳遞給 2
2 就會把八卦傳遞給 3

※2008/10/18 測資範圍更正 by peter50216,感謝 surwdkgo。

Problem Source

原TIOJ1451 / 建中校內培訓第二次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 8000 65536 262144 1
1 8000 65536 262144 2
2 8000 65536 262144 3
3 8000 65536 262144 4
4 8000 65536 262144 5
5 8000 65536 262144 6
6 8000 65536 262144 7
7 8000 65536 262144 8
8 8000 65536 262144 9
9 8000 65536 262144 10
10 8000 65536 262144 11