7023 - Friends   

Description

清大某研究室為了分析新竹市民的社群分布情形,他們在火車站前找了N個人出來來取樣

統計,因為人數太多,所以他們採取了一策略,就是隨便抓兩個人出來問他們之間是不是

朋友,當他們發現A和B是朋友的時候,就會紀錄下來,在不知道幾次的詢問下,他們總共

記錄了M筆兩個人之間是朋友的資料。

但是沒有調查完所有人之間的關係,所以他們就用一種Heruistic的作法,只要A和B是朋友,

B和C也是朋友,朋友的朋友就是朋友,所以A和C也會是朋友,根據這種做法,他們可以

把所有有朋友關係的人都視為同一個社群,他們要計算出這些人中,社群人數最大的團體

一共有幾個人,請你寫程式幫忙他們計算該值。

Input

第一行有一個正整數表示有幾筆測試資料

每筆測試資料第一行有兩個正整數 N (1 <= N <= 30,000), M (0 <= M <= 500,000)

表示取樣的人數和記錄為朋友關係的資料筆數

接下來M行有兩個正整數A, B (1 <= A <= N, 1 <= B <= N, A != B)

表示第A個人和第B個人之間是朋友

Output

對於每筆測試資料,輸出這些人中,最大的社群有幾個人

Sample Input  Download

Sample Output  Download

Tags




Discuss