TopCoder

Thumb c1c8af6a6ee436c5994d03cb1a44b7da
$nA-NIl$
$After$ $Four$ $Years !$

User's AC Ratio

95.6% (43/45)

Submission's AC Ratio

41.7% (70/168)

Tags

uva

Description

給你一張有向圖G(可能有自環或重邊),考慮以下轉換:

首先,建構一張新的圖T(G),頂點集跟原圖G一樣。

在T(G)存在一條有向邊u→v若且唯若在G中存在一條u到v的路徑(path)。

符合這個條件的T(G)我們稱他是G的傳遞閉包(Transitive Closure)。

我們定義有向圖中的集團(Clique)是一個點集合U,

對任何集合內的兩個點u,v,必定存在一條u→v或v→u的有向邊。

集團的大小定義為這個集團的頂點個數。

現在給你一張圖G,請求出T(G)的最大集團大小。

Input Format

輸入的第一行包含一個正整數T表示測資筆數。

每筆測資的第一行包含兩個數字N, M,其中0 <= N <= 10,000、0 <= M <= 100,000。

N表示圖G中的頂點個數(編號1~N)、M表示圖G中的有向邊數。

接下來會有M行,每行兩個整數U, V,表示G中有一條U→V的有向邊。

Output Format

對每筆測資輸出一行包含一個數字K表示T(G)的最大集團大小。

Sample Input

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

Sample Output

4

Hints

2018/3/9 測資修正

Problem Source

原TIOJ1683 / UVa 11324 (測資範圍加大)

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 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3