题目链接：http://codeforces.com/gym/102900/problem/K

、

题目大意：给一个图，每个点一开始为低价点或高价点，一商人从点0出发（点0一开始必定为低价点），按低价买入——高价卖出的顺序走，每个点被走过后高价变为低价，低价变为高价，问该图是否能够无限地走下去。

 

题目思路：首先，不妨记低价为0，高价为1，走的路径必定为0-1-0-1......若要无限走下去则一定要存在一条0-1链且首尾相同。那么首先用所有的0-1边建图， 在这个新图上枚举同色边。

但什么情况下才会满足题意呢？只有从点0开始分别走过同色边两个点且过程中无重复点走过才满足题意。

首先，以点0为根先建立新图的dfs树，记同色边两顶点分别为u，v。

可以明显知道当u是v的祖先或v是u的祖先时一定满足题意（即该同色边为返祖边）。

那同色边是横向边的时候有可能一笔走到吗？ 这是有可能的，记L=lca(u, v)，当L的父亲与u（或v）在同一个边双连通分量时，即可满足题意，走法为fa[L]-->u-->L-->v。

 

update：

（做法假了好像，应该是点双而不是边双）

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Edge{
    int to,nxt;
}edge[400100];
struct lwd{
    int u,v;
}b[200100];
int head[200100],num,cnt;
int n,m,a[200100],f[200100][20],lg[200100],dep[200100];
int dfn[200100],low[200100],cnt2,col[200100],bridge[400100];
char op[200100];
bool vis[200100];
void add(int u,int v){
    edge[++num].to=v;
    edge[num].nxt=head[u];
    head[u]=num;
}
void dfs(int now,int fa,int depth){
    dep[now]=depth;
    f[now][0]=fa; vis[now]=1;
    for(int i=1;(1<<i)<=depth;i++) f[now][i]=f[f[now][i-1]][i-1];
    for(int i=head[now];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if (vis[v]) continue;
        dfs(v,now,depth+1);
    }
}

void tarjan(int u,int id){
    low[u]=dfn[u]=++cnt2;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if (!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if (low[v]>dfn[u]) bridge[i]=bridge[i^1]=1;
        }
        else if (id==-1||(id^1)!=i) low[u]=min(low[u],dfn[v]);
    }
}

void dfs2(int u,int fa){
    col[u]=cnt2; vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if (vis[v]) continue;
        if (bridge[i]) continue;
        dfs2(v,u);
    }
}

int lca(int u,int v){
    if (dep[u]==-1||dep[v]==-1) return -1;
    if (dep[u]>dep[v]) u^=v^=u^=v;
    while(dep[v]>dep[u]){
        v=f[v][lg[dep[v]-dep[u]]];
    }
    if (u==v) return u;
    int max_dep=lg[dep[u]];
    for(int i=max_dep;i>=0;i--){
        if (f[u][i]!=f[v][i]){
            u=f[u][i]; v=f[v][i];
        }
    }
    return f[u][0];
}

int main()
{
    int T,u,v;
    scanf("%d",&T);
    lg[1]=0;
    for(int i=2;i<=200005;i++){
        if ((1<<(lg[i-1]+1))==i) lg[i]=lg[i-1]+1;
        else lg[i]=lg[i-1];
    }
    while(T--){
        bool zx=0;
        num=-1; cnt=0; cnt2=0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<2*m;i++) bridge[i]=0;
        for(int i=0;i<n;i++) dfn[i]=low[i]=0;
        for(int i=0;i<n;i++) dep[i]=head[i]=-1;
        for(int i=0;i<n;i++) col[i]=0;
        for(int i=0;i<20;i++){
            for(int j=0;j<n;j++) f[j][i]=-1;
        }
        scanf(" %s",op);
        for(int i=0;i<n;i++){
            if (op[i]=='L') a[i]=0;
            else a[i]=1;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            if (a[u]!=a[v]){
                add(u,v); add(v,u);
            }
            else{
                b[++cnt].u=u; b[cnt].v=v;
            }
        }
        for(int i=0;i<n;i++) vis[i]=0;
        dfs(0,-1,0);
        for(int i=0;i<n;i++){
            if (!dfn[i]) tarjan(i,-1);
        }
        cnt2=0;
        for(int i=0;i<n;i++) vis[i]=0;
        for(int i=0;i<n;i++){
            if (!vis[i]){
                cnt2++;
                dfs2(i,-1);
            }
        }
        for(int i=1;i<=cnt;i++){
            int L=lca(b[i].u,b[i].v);
            if (L==-1) continue;
            if (L==b[i].u||L==b[i].v){
                printf("yes\n");
                zx=1;
                break;
            }
            if (L==0) continue;
            if (col[b[i].u]==col[f[L][0]]||col[b[i].v]==col[f[L][0]]){
                printf("yes\n");
                zx=1;
                break;
            }
        }
        if (!zx) printf("no\n");
    }
    return 0;
}