题目给的太裸，显然2sat；
还是用i表示xi=true(1), i+n表示xi=false(0)
这题唯一要说的是一种情况，当xi必须=true或xi必须=false这种情况下怎么弄
比如这道题出现的 假如条件要求xi or xj=0 那么
除了i+n--->j+n ,j+n--->i+n这两条边外
显然还要xi，xj都必须取false
这种情况我们好像不好用“推导出”的原理建边，
考虑这样的情况1，假如存在路径i+n--->i,但不存在路径i--->i+n
为什么这种情况是有解的，这是因为我们我们可以取i这个状态，这样就成立了，而取i+n这个状态是不成立的
现在我们要求一定只能取i+n这个状态
我们就连边i--->i+n
假如是情况1，加上这条边后，显然无解，符合。
假如i和i+n间都没有路径，显然加了这条边之后，就转化为情况1，这样显然只能取i+n这个状态
假如原来无解，加了边之后现在当然也无解
所以，对于xi,not xi，我们一定要取xi的话
我们就连边xi<--- not xi,这样就可以了
1 type node=record 2 next,point:longint; 3 end; 4 5 var edge:array[0..4000010] of node; 6 v,f:array[0..10010] of boolean; 7 be,st,dfn,low,p:array[0..10010] of longint; 8 sum,h,t,a,b,c,i,n,m,len:longint; 9 s:string; 10 11 function min(a,b:longint):longint; 12 begin 13 if a>b then exit(b) else exit(a); 14 end; 15 16 procedure add(x,y:longint); 17 begin 18 inc(len); 19 edge[len].point:=y; 20 edge[len].next:=p[x]; 21 p[x]:=len; 22 end; 23 24 procedure tarjan(x:longint); 25 var i,y:longint; 26 begin 27 inc(h); 28 dfn[x]:=h; 29 low[x]:=h; 30 inc(t); 31 st[t]:=x; 32 f[x]:=true; 33 v[x]:=true; 34 i:=p[x]; 35 while i<>-1 do 36 begin 37 y:=edge[i].point; 38 if not v[y] then 39 begin 40 tarjan(y); 41 low[x]:=min(low[x],low[y]); 42 end 43 else if f[y] then low[x]:=min(low[x],low[y]); 44 i:=edge[i].next; 45 end; 46 if dfn[x]=low[x] then 47 begin 48 inc(sum); 49 while st[t+1]<>x do 50 begin 51 y:=st[t]; 52 f[y]:=false; 53 be[y]:=sum; 54 dec(t); 55 end; 56 end; 57 end; 58 59 60 begin 61 fillchar(p,sizeof(p),255); 62 readln(n,m); 63 for i:=1 to m do 64 begin 65 read(a,b,c); 66 inc(a); 67 inc(b); 68 readln(s); 69 if s=' AND' then 70 begin 71 if c=0 then 72 begin 73 add(a,b+n); 74 add(b,a+n); 75 end 76 else begin 77 add(a,b); 78 add(b,a); 79 add(a+n,a); 80 add(b+n,b); 81 end; 82 end 83 else if s=' OR' then 84 begin 85 if c=0 then 86 begin 87 add(a+n,b+n); 88 add(b+n,a+n); 89 add(a,a+n); 90 add(b,b+n); 91 end 92 else begin 93 add(a+n,b); 94 add(b+n,a); 95 end; 96 end 97 else if s=' XOR' then 98 begin 99 if c=0 then 100 begin 101 add(a+n,b+n); 102 add(b+n,a+n); 103 add(a,b); 104 add(b,a); 105 end 106 else begin 107 add(a+n,b); 108 add(a,b+n); 109 add(b+n,a); 110 add(b,a+n); 111 end; 112 end; 113 end; 114 for i:=1 to 2*n do 115 if not v[i] then 116 begin 117 h:=0; 118 t:=0; 119 tarjan(i); 120 end; 121 122 for i:=1 to n do 123 if be[i]=be[i+n] then 124 begin 125 writeln('NO'); 126 halt; 127 end; 128 writeln('YES'); 129 end.