#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int N = 60;
const int M = N * N;
int map[N][10];
int len[N];
int L[16*N*N], R[16*N*N], U[16*N*N], D[16*N*N], Sum[16*N*N], Row[16*N*N], Col[16*N*N];
int ans[16*N];
int id, anslen, r;
int H[16*N];
bool OK;
int n, m;
int lenx;
int deep;
void pre() {
for(int i = 0; i <= n; i ++) {
L[i] = i - 1;
R[i] = i + 1;
U[i] = D[i] = i;
Sum[i] = 0;
}
L[0] = n; R[n] = 0;
id = n + 1;
}
inline void insert(int i, int *xx) {
for(int j = 0; j < lenx; j ++, id ++) {
int x = xx[j];
Row[id] = i;
Col[id] = x;
Sum[x] ++;
U[id] = x;
D[id] = D[x];
U[D[x]] = id;
D[x] = id;
if( j == 0 ) {
L[id] = R[id] = id;
} else {
L[id] = id - 1;
R[id] = id - j;
R[id-1] = id;
L[id-j] = id;
}
}
}
//n*2^4 * n
//void build() {
// int x[6];
// r = 0;
// for(int i = 1; i <= n; i ++) {
// for(int j = 0; j < (1<<len[i]); j ++) {
// lenx = 0;
// r ++;
// x[lenx++] = i;
// for(int k = 0; k < len[i]; k ++) {
// if( ((1<<k) & j) )x[lenx++] = map[i][k];
// }
// //for(int i = 0; i < lenx; i ++) printf("%d ", x[i]); puts("");
// //system("pause");
// //H[r] = i;
// insert(r, x);
// }
// }
// //pr/intf("%d\n", r);
//}
// n * n
void build() {
int x[6];
for(int i = 1; i <= n; i ++) {
lenx = 0;
x[lenx++] = i;
for(int j = 0; j < len[i];j ++) {
x[lenx ++] = map[i][j];
}
insert(i, x);
}
}
void remove(int &c) {
for(int i = D[c]; i != c ; i = D[i]) {
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void resume(int &c) {
for(int i = U[c]; i != c ; i = U[i]) {
L[R[i]] = i;
R[L[i]] = i;
}
}
inline int Astar() {
int res = 0;
bool vis[60] = {false};
for(int i = R[0]; i != 0; i =R[i]) {
if( !vis[ i ] ) {
vis[ i ] = true;
res ++;
for(int j = D[i]; j != i; j = D[j]) {
for(int k = R[j]; k != j; k = R[k]) {
vis[ Col[k] ] = true;
}
}
}
}
return res;
}
void dfs(int dep) {
if( Astar() + dep > deep ) return ;
if(R[0] == 0) {
anslen = dep;
OK = true;
return;
}
int i,j,idx = R[0];
for(i = R[0] ; i != 0 ; i = R[i]) {
if(Sum[i] < Sum[idx]) {
idx = i;
if( Sum[idx] <= 1 ) break;
}
}
for(i = D[idx] ; i != idx; i = D[i]) {
remove(i);
for(j = R[i] ; j != i ; j = R[j]) remove(j);
dfs( dep + 1 );
for(j = L[i] ; j != i ; j = L[j]) resume(j);
resume(i);
if( OK ) return;
}
}
int main() {
freopen("in.txt","r",stdin);
while( scanf("%d %d", &n, &m) != EOF ) {
memset(len, 0, sizeof( len ));
for(int i = 0; i < m; i ++) {
int s, t;
scanf("%d %d", &s, &t);
map[s][len[s]++] = t;
map[t][len[t]++] = s;
}
pre();
build();
deep = 1;
OK = false;
anslen = n;
while( !OK ) {
dfs(0);
deep ++;
}
printf("%d\n", anslen);
}
while(1);
return 0;
}
n*n的建模 然后找最少的行数使得每一列至少有一个'1'