TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

60.9% (14/23)

Description

資訊科學中的有向圖(Directed-Graph)是一種很有趣的資料結構。

今天你研發出了一種加密有向圖的方式:

加密的圖形中有 m 個頂點,分別來自原始圖的每一條邊。

當原始圖的PA→PB以及PB→PC存在時,則在加密的圖形中劃上一條PAB→PBC

現在你得到了一個加密之後的圖形,但是你擔心加密的過程中是否有問題,所以你決定判斷一下他是否是一個經過正確加密過的圖形。

Input Format

本題有多組測試資料:

第一行有一個數字 T ,代表有 T 組圖形需要判斷

每組測試資料的:

第一行有一個數字 n ,代表這組圖形中有 n 個點。( 0 < n <= 500)

第二行有一個數字 m ,代表這組圖形中有 m 條邊。( 0 <= m <= 100,000)

接下來有 m 行,每行有兩個數字ai,bi,代表從ai到bi有一條有向邊

Output Format

對於每筆測試資料輸出是否是經過正確加密過的圖形。

Sample Input

4
2
1
0 1
5
0
4
3
0 1
2 1
2 3
3
9
0 1
0 2
1 2
1 0
2 0
2 1
0 0
1 1
2 2

Sample Output

Case #1: Yes
Case #2: Yes
Case #3: No
Case #4: Yes

Hints

※2008/10/29 題目敘述補注 by hallogameboy。感謝 akira。

Problem Source

原TIOJ1457 / 建中校內培訓第三次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:Uva 11175)

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144
10 3000 65536 262144