TopCoder

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

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

48.8% (20/41)

Tags

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 1

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 1

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

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 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
10 3000 65536 262144 11