1 /**************************************************************
2 Problem: 1006
3 User: AsmDef
4 Language: C++
5 Result: Accepted
6 Time:1432 ms
7 Memory:12424 kb
8 ****************************************************************/
9
10 /*====================Asm.Def========================*/
11 #include <iostream>
12 #include <cctype>
13 #include <cstdio>
14 #include <vector>
15 using namespace std;
16 inline void getd(int &x){
17 char c = getchar();
18 bool minus = 0;
19 while(!isdigit(c) && c != ‘-‘)c = getchar();
20 if(c == ‘-‘)minus = 1, c = getchar();
21 x = c - ‘0‘;
22 while(isdigit(c = getchar()))x = x * 10 + c - ‘0‘;
23 if(minus)x = -x;
24 }
25 /*======================================================*/
26 const int maxn = 10002;
27 vector<int> adj[maxn];
28 int N, color[maxn] = {0}, ans = 0, adjcnt[maxn] = {0};
29 inline void init(){
30 int a, b, M;
31 getd(N), getd(M);
32 while(M--){
33 getd(a), getd(b);
34 adj[a].push_back(b);
35 adj[b].push_back(a);
36 }
37 }
38 inline void work(){
39 int i, j, lim, tmp = 1, Max = 0;
40 bool ok_col[maxn];
41 lim = (int)adj[1].size();
42 color[1] = 1;
43 for(i = 0;i < lim;++i)
44 if(!color[adj[1][i]]) ++adjcnt[adj[1][i]];
45 for(i = 1;i < N;++i){
46 Max = 0;
47 for(j = 1;j <= N;++j){
48 ok_col[j] = 1;
49 if(!color[j] && adjcnt[j] > Max)tmp = j, Max = adjcnt[j];
50 }
51 lim = (int)adj[tmp].size();
52 for(j = 0;j < lim;++j)
53 ok_col[color[adj[tmp][j]]] = 0;
54 for(j = 1;j <= N;++j) if(ok_col[j])break;
55 color[tmp] = j;
56 if(j > ans)ans = j;
57 lim = (int)adj[tmp].size();
58 for(j = 0;j < lim;++j)
59 if(!color[adj[tmp][j]]) ++adjcnt[adj[tmp][j]];
60 }
61 printf("%d\n", ans);
62 }
63 int main(){
64 init();
65 work();
66 return 0;
67 }
