飞机票：http://poj.org/problem?id=3678

分析：题意。。。就是说给你个有向图，然后给你变a b 且a b有个值为c 要求a的值op b的值=c 其中op为（&，|，^）位运算，求解是否可以求出这样的解。继续2-sat。。。这题怎么搞呢。。。其实只要知道为位运算相互间的限制然后建图求解即可。。。那么关系是什么呢。。。不妨设当前点i为1则是i*2,为0则是i*2+1那么就可以建图了

AND 结果为1：建边 x*2+1->x*2,y*2+1->y*2 （两个数必须全为1）

AND 结果为0：建边 y*2->x*2+1,x*2->y*2+1 （两个数至少有一个为0）

OR 结果为1：建边 x*2+1->y*2,2*y+1->x*2 （两个数至少有一个为1）

OR 结果为0：建边 x*2->x*2+1,y*2->y*2+1 （两个数必须全为0）

XOR 结果为1：建边 x*2->y*2+1,y*2->x*2+1,y*2+1->x*2,x*2+1->y*2 （两个数必须不同）

XOR 结果为0：建边 x*2->y*2,y*2->x*2,x*2+1->y*2+1,y*2+1->x*2+1 （两个数必须相同）

然后建边就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=2345;
vector<int> V[maxn];
int n,m;
char ch[100];
void init()
{
    for(int i=0; i<=2*n; i++)V[i].clear();
    int u,v,c;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d%s",&u,&v,&c,ch+1);
        u=u*2;
        v=v*2;
        if(ch[1]=='A')
        {
            if(c==0)
            {
                V[u].push_back(v^1);
                V[v].push_back(u^1);
            }
            else
            {
                V[u^1].push_back(u);
                V[v^1].push_back(v);
            }
        }
        else if(ch[1]=='O')
        {
            if(c==0)
            {
                V[u].push_back(u^1);
                V[v].push_back(v^1);
            }
            else
            {
                V[u^1].push_back(v);
                V[v^1].push_back(u);
            }
        }
        else
        {
            if(c==0)
            {
                V[u].push_back(v);
                V[v].push_back(u);
                V[u^1].push_back(v^1);
                V[v^1].push_back(u^1);
            }
            else
            {
                V[u].push_back(v^1);
                V[v].push_back(u^1);
                V[v^1].push_back(u);
                V[u^1].push_back(v);
            }

        }
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*n; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<n; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("NO\n");
            return;
        }
    }
    printf("YES\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}