记录编号	26086	评测结果	AAAAAAAAAAAAAAAAA
题目名称	牛棚的灯	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.022 s
提交时间	2011-07-23 07:58:41	内存使用	0.12 MiB

{[Usaco2009 Nov]lights 灯 bzoj1770
 高斯消元解异或方程组 位运算优化 搜索dfs
 Author: yangbohua
 Time: 2011-06-22}
 
program bzoj1770;
var
  a,p:array[0..40] of int64;
  b:array[0..40] of boolean;
  n,m,i,j,k,h,ans,r1,r2:longint;
  e,temp:int64;
  
procedure dfs(i,h,s:longint);
var
  j:longint;
begin
  if s>=ans then exit;
  if i<=0 then
  begin 
    if s<ans then ans:=s;
    exit;
  end; 
  if b[i] then
  begin
    p[i]:=0;
    dfs(i-1,h,s);
    p[i]:=1;
    dfs(i-1,h,s+1);
  end
  else
  begin
    p[i]:=a[h] and e;
    for j:=i+1 to n do
      p[i]:=p[i] xor (((a[h] shr (n-j+1)) and e)*p[j]);
    dfs(i-1,h-1,s+p[i]);
  end;
end;      
  
begin
  assign(input,'lights.in');
  reset(input);
  assign(output,'lights.out');
  rewrite(output);
  
  fillchar(a,sizeof(a),0);
  readln(n,m);
  e:=1;
  for i:=1 to n do
  begin
    a[i]:=a[i] or (e shl (n-i+1));
    a[i]:=a[i]+1;
  end;
  for i:=1 to m do
  begin
    readln(r1,r2);
    a[r1]:=a[r1] or (e shl (n-r2+1));
    a[r2]:=a[r2] or (e shl (n-r1+1));
  end;
  
  k:=1;
  fillchar(b,sizeof(b),false);
  for i:=1 to n do
  begin
    j:=k;
    while (j<=n) and ((a[j] and (e shl (n-i+1)))=0) do
      inc(j);
    if j<=n then
    begin
      if k<j then
      begin
        temp:=a[k]; a[k]:=a[j]; a[j]:=temp;
      end;
      for h:=k+1 to n do
        if (a[h] and (e shl (n-i+1)))>0 
          then a[h]:=a[h] xor a[k];
      k:=k+1;
    end
    else b[i]:=true;
  end;      
  
  ans:=n;
  fillchar(p,sizeof(p),0);
  dfs(n,k-1,0);
  writeln(ans);
  
  close(input);
  close(output);
end.