TopCoder

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

User's AC Ratio

87.5% (21/24)

Submission's AC Ratio

23.4% (60/256)

Tags

Description

一個有向圖是由點集 V 以及邊集 E ∈ {V x V} 所組成。

一條有向邊(u,v)代表有一條由 u 指向 v 的邊(而(v,u)則是反方向)。

而一個有向圈則是由有向圖中的邊集:(u1, v1), (u2, v2),…, (uk, vk),所組成,並且ui+1 = vi for i = 1, …, k-1, u1=vk.

如果有向圈不重複經過同一頂點即可達成圈的特性,我們則稱其為簡單圈。

強連通圖則是指有向圖內的任兩點皆可找到路徑達到彼此。

現在我們發明出了一種性質『仙人掌』性質:當一個圖屬於強連通圖 且 每條邊都恰屬於一個簡單圈 時,我們稱其具有『仙人掌』性質。

在上圖中,左邊的圖很明顯符合『仙人掌』性質,但在右邊的圖中,(0,1)這條邊被兩條簡單圈所包含,所以他不屬於『仙人掌』性質。

現在給你很多圖,你能判斷他們哪些屬於『仙人掌』性質嗎?

Input Format

本題有多筆測試資料:

第一行有一個數字T,代表接下來有 T 個圖需要判斷。
每筆資料的:
第一行有一個數字 n ,代表圖中有 n 個點。 ( n <=105)
第二行有一個數字 m ,代表圖中有 m 條邊。
接下來有 m 行,每行有兩個數字a,b,代表存在一條(a,b)的有向邊

Output Format

對於每筆測試資料輸出是否符合『仙人掌』性質。
若符合請輸出"YES"(不含雙引號)
若不符合請輸出"NO"(不含雙引號)

Sample Input 1

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

Sample Output 1

YES
NO

Hints

Problem Source

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

Subtasks

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

Testdata and Limits

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