飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3819

题意：就是有个人叫DD，他参见乒乓球比赛，然后要拿冠军，(就是赢得场数最多的人),给你m个初始的结果和下面还要比的场次，问DD能否拿冠军，其中只能有一个冠军(即不能有多个最大值)

分析:一看这道题，就知道贪心取DD能赢的最大值，即加入DD已经赢了p场，然后他下面还比了q场，贪心的话，他最多能赢p+q场，所以其余的人最多只能赢p+q-1场，因为不能有一样的最大值。先判断当前每个人已经赢了的场数，假设p+q=a1,别人当前赢得场数为a2。a3...an，如果a2到an其中有大于等于a1那么直接就是no了，因为不管怎么比，都不可能比a1小了如果都小于a1的话，就必须找个方法判断到底行不行？从前面可以知道第i个人最多只能赢a1-ai-1场，这样才小于a1,设为b2.b2..b3，然后假设第i个人和其他人除了DD一共比了k场，那么他最多只能赢bi场，因为限制。然后就是想什么方法判断每个人都满足。这里就用到了最大流算法。假设有个源点s，假如每对人i和j比了kij场，那么就有从s流kij的流量到i和j，我们可以定义为点vij,然后vij可以流向vi和vj，因为这个没有限制，但是可以定义为kij，因为最大了.最后我们可以定义个汇点，然后从vi流bi个流量到t，因为最大只能是bi，最后跑一边最大流，看它能不能是一个可行流，即除了和DD比的场数之外，所有的场数是否可以满足要求。最后啪啪啪就可以AC了。

/*
Author:Chieh
Because Of Coding
*/
/*
O(E^2 V)
E//边数
V//节点
//每次按最短的s-t路径进行增广
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=5*12;
map<string,int> M;
struct he
{
    int to,val,id;
};
vector<he> V[3000];
int n,m;
char ch1[12],ch2[12],ch3[12];
int win[maxn];
int next[maxn][maxn];
int Link[maxn][maxn];
void init()
{
    for(int i=1; i<3000; i++)
    {
        V[i].clear();
    }
    M.clear();
    ch1[1]='D';
    ch1[2]='D';
    ch1[3]='\0';
    M[ch1+1]=1;
    memset(win,0,sizeof(win));
    memset(next,0,sizeof(next));
    int st=1;
    for(int i=1; i<=m; i++)
    {
        scanf("%s%s%s",ch1+1,ch2+1,ch3+1);
        if(M[ch1+1]==0)
        {
            M[ch1+1]=++st;
        }
        if(M[ch2+1]==0)
        {
            M[ch2+1]=++st;
        }
        int t1=M[ch1+1];
        int t2=M[ch2+1];
        if(ch3[1]=='w')
        {
            win[t1]++;
        }
        else
        {
            win[t2]++;
        }
    }
    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%s%s",ch1+1,ch2+1);
        if(M[ch1+1]==0)
        {
            M[ch1+1]=++st;
        }
        if(M[ch2+1]==0)
        {
            M[ch2+1]=++st;
        }
        int t1=M[ch1+1];
        int t2=M[ch2+1];
        if(t1>t2)swap(t1,t2);
        next[t1][t2]++;
    }
    for(int i=2; i<=n; i++)
    {
        win[1]+=next[1][i];
    }
}
int fa[3000];
int idx[3000];
bool vis[3000];
bool BFS(int s,int t)
{
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    fa[s]=s;
    vis[s]=1;
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        if(now==t)return 1;
        for(int i=0; i<V[now].size(); i++)
        {
            int u=V[now][i].to;
            int w=V[now][i].val;
            if(w>0&&!vis[u])
            {
                vis[u]=1;
                fa[u]=now;
                idx[u]=i;
                Q.push(u);
            }
        }
    }
    return 0;
}
void play()
{
    for(int i=2; i<=n; i++)
    {
        if(win[i]>=win[1])
        {
            printf("No\n");
            return;
        }
    }//判断是否没开始就不能满足了
    int st=1;
    for(int i=2; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            Link[i][j]=++st;
        }
    }
    for(int i=2; i<=n; i++)
    {
        Link[i][i]=++st;
    }
    st++;
    LL com=0;
    for(int i=2; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            if(next[i][j]!=0)
            {
                int val=next[i][j];
                int v=Link[i][j];
                com+=val;
                V[1].push_back((he)
                {
                    v,val,V[v].size()
                });
                V[v].push_back((he)
                {
                    1,0,V[1].size()-1
                });
                int u1=Link[i][i];
                int u2=Link[j][j];
                V[v].push_back((he)
                {
                    u1,val,V[u1].size()
                });
                V[u1].push_back((he)
                {
                    v,0,V[v].size()-1
                });
                V[v].push_back((he)
                {
                    u2,val,V[u2].size()
                });
                V[u2].push_back((he)
                {
                    v,0,V[v].size()-1
                });
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        int id=Link[i][i];
        int val=win[1]-win[i]-1;
        V[id].push_back((he)
        {
            st,val,V[st].size()
        });
        V[st].push_back((he)
        {
            id,0,V[id].size()-1
        });
    }

    LL MAX=0;
    while(BFS(1,st))
    {
        int MIN=2*INF;
        int now=st;
        while(fa[now]!=now)
        {
            int f=fa[now];
            int id=idx[now];
            MIN=min(MIN,V[f][id].val);
            now=f;
        }
        MAX+=MIN;
        now=st;
        while(fa[now]!=now)
        {
            int f=fa[now];
            int id=idx[now];
            int idd=V[f][id].id;
            V[f][id].val-=MIN;
            V[now][idd].val+=MIN;
            now=f;
        }
    }
    if(MAX==com)printf("Yes\n");
    else printf("No\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}