题目：
农夫约翰有N只奶头，这N只奶牛分别属于三个种类：A，B，C。但是不幸的是，约翰忘记了每只奶牛分别属于哪个种类了。他仅仅只记得的K个奶牛之间的关系。例如，他记得奶牛1和奶牛2是同一种类，或者奶牛1和奶牛5是不同种类的。
问题描述：
给定这K个关系，请帮助约翰计算这N只奶牛可能的种类分布情况共有多少种。（当K个关系本身就是矛盾的时候，答案是0）。
农夫约翰有N只奶头，这N只奶牛分别属于三个种类：A，B，C。但是不幸的是，约翰忘记了每只奶牛分别属于哪个种类了。他仅仅只记得的K个奶牛之间的关系。例如，他记得奶牛1和奶牛2是同一种类，或者奶牛1和奶牛5是不同种类的。
问题描述：
给定这K个关系，请帮助约翰计算这N只奶牛可能的种类分布情况共有多少种。（当K个关系本身就是矛盾的时候，答案是0）。
题解：
搜索。
代码：
varn,m,ans:longint;a,b:array[0..15] of longint;c:array[1..15] of boolean;f:array[1..15,1..15] of longint;
function main(x,y,z:longint):boolean;
vari:longint;
beginfor i:=1 to x doif ((f[b[i],y]=1)and(z<>a[i]))or((f[b[i],y]=2)and(z=a[i])) thenexit(false);exit(true);
end;
procedure dfs(t:longint);
vari:longint;
beginif t>b[0] thenbegininc(ans);exit;end;for i:=1 to 3 doif main(t-1,b[t],i) thenbegininc(a[0]);a[a[0]]:=i;dfs(t+1);a[a[0]]:=0;dec(a[0]);end;
end;
procedure init;
vari,x,y:longint;s:char;
beginreadln(n,m);fillchar(c,sizeof(c),true);for i:=1 to m dobeginreadln(s,x,y);if c[x] thenbeginc[x]:=false;inc(b[0]);b[b[0]]:=x;end;if c[y] thenbeginc[y]:=false;inc(b[0]);b[b[0]]:=y;end;if s='S' thenbeginf[x,y]:=1;f[y,x]:=1;endelsebeginf[x,y]:=2;f[y,x]:=2;end;end;
end;
vari:longint;
beginassign(input,'assign.in'); reset(input);assign(output,'assign.out'); rewrite(output);init;dfs(1);for i:=1 to n-b[0] doans:=ans*3;writeln(ans);close(input); close(output);
end.
