TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

96.0% (96/100)

Submission's AC Ratio

52.4% (151/288)

Description

給你一個有向圖(directed graph),請問該圖的最小圈(cycle)長度為何?

Input Format

輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有兩個正整數 $n, m$,
$1 \le n \le 500 ; 1 \le m \le 250000$,代表該圖的點數和邊數。
頂點的編號從 $1$ 到 $n$。
接下來有 $m$ 列,每列用兩個整數 $i, j$($1 \le i, j \le n$)描述一條有向邊,從編號 $i$ 到編號 $j$。
當 $n=m=0$ 時代表輸入結束。你可以假設輸入的圖不會有自環(self-cycle)的出現。

Output Format

對於每筆測試資料,請輸出最小圈的邊長。如果該圖沒有圈,請輸出 $0$。

Sample Input

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

Sample Output

4

Hints

範例輸入當中,最小的 cycle 為 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1$ 或 $1 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 1$

Problem Source

原TIOJ1212 / TIOJ 2008例行賽03 (prob D)。經典問題練習。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3