TopCoder

Thumb emilia
rsabcmoi
Yes? No? Yes! Yes!

User's AC Ratio

71.7% (38/53)

Submission's AC Ratio

18.0% (85/471)

Description

某間公司有n個員工。這n個員工之間可能有些人會有互相的電話號碼。現在這間公司的老闆希望能夠將這n個員工重新分配到辦公室,為了維護工作環境的品質,辦公室越多越好(這樣相對地大家空間會變大)。但是為了維持工作效率,老闆希望不同辦公室的任何兩個人,都必須擁有對方的電話號碼。

請問最多能將這些員工分成幾間辦公室呢?

Input Format

每個輸入檔包含一筆測試資料。
第一列有一個正整數n(1<=n<=100,000),代表員工數量。(員工編號為1到n)
第二列有一個整數m(0<=m<=2,000,000),代表互相知道電話的員工對數。
接下來有m列,每一列有兩個相異正整數x,y(1<=x,y<=n)代表員工編號。

Output Format

請輸出最大的辦公室數量。

Sample Input

7
16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7

Sample Output

3

Hints

{4}, {5,7}, {1,2,3,6}
2016.12.22 題敘測資範圍修正 by hansonyu123

Problem Source

原TIOJ1220 / TIOJ 2008例行賽03-Elite (prob B)。POI 2006/2007 Stage I(prob 1,BIU)。Problem Setter:Tmt,kelvin。

Subtasks

For Testdata: 0 ~ 0, Score: 7
For Testdata: 1 ~ 1, Score: 7
For Testdata: 2 ~ 2, Score: 7
For Testdata: 3 ~ 3, Score: 7
For Testdata: 4 ~ 4, Score: 7
For Testdata: 5 ~ 5, Score: 7
For Testdata: 6 ~ 6, Score: 7
For Testdata: 7 ~ 7, Score: 7
For Testdata: 8 ~ 8, Score: 7
For Testdata: 9 ~ 9, Score: 7
For Testdata: 10 ~ 10, Score: 7
For Testdata: 11 ~ 11, Score: 7
For Testdata: 12 ~ 12, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144
1 5000 65536 262144
2 5000 65536 262144
3 5000 65536 262144
4 5000 65536 262144
5 5000 65536 262144
6 5000 65536 262144
7 5000 65536 262144
8 5000 65536 262144
9 5000 65536 262144
10 5000 65536 262144
11 5000 65536 262144
12 5000 65536 262144