TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

94.1% (32/34)

Submission's AC Ratio

38.2% (52/136)

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

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 65536 262144
1 1500 65536 262144
2 1500 65536 262144