n695. 11175 - From D to E and back
Tags :
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-15 13:51

Content

取任意有向圖 D,其包含 n 個頂點和 m 條邊。你可以通過以下方式構造 B 的對應圖 E。E 將有 m 個頂點,每個頂點對應 D 的一條邊。例如,如果 D 有一條邊 uv,那麼 E 將有一個頂點稱為 uv。現在,當 D 有邊 uv 和 vw 時,E 將有一條從頂點 uv 到頂點 vw 的邊。E 中沒有其他邊。

給定一個圖 E,你需要判斷是否存在某個有向圖 D,使得 E 可以作為該有向圖 D 的對應圖。

Input

輸入的第一行給出案例的數量 N (N < 220)。接下來是 N 個測試案例。每個案例以兩行開始,包含 m (0 ≤ m ≤ 300) 和 k。接下來的 k 行每行包含一對頂點 x 和 y,表示在 E 中存在一條從 x 到 y 的邊。頂點的編號從 0 到 m − 1。

Output

對於每個測試案例,輸出一行,內容為 'Case #x:',後跟 'Yes' 或 'No',取決於 E 是否為有效的對應圖。注意,D 允許有重複邊和自環。

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
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」