Description

现在你有一张无向图包含n个节点m条边。最初，每一条边都是蓝色或者红色。每一次你可以将一个节点连接的所有边变色（从红变蓝，蓝变红）。

找到一种步数最小的方案，使得所有边的颜色相同。

 

Input

第一行包含两个数n,m（1<=n,m<=100000）分别代表节点数和边的数量

接下来m行描述边，第i行ui,vi,ci，代表ui有一条颜色为ci的边与vi相连（ci是B或者是R），B代表蓝色，R代表红色。数据保证没有自环的边。

Output

如果没有方案就输出-1。否则第一行输出k代表最小的步数

 

Sample Input

输入1：3 31 2 B3 1 R3 2 B输入3：4 51 2 R1 3 R2 3 B3 4 B1 4 B

Sample Output

输出1：1输出3：-1

 

Data Constraint

对于30%数据，n<=20,m<=20

分析

非常简单的染色问题

我们分两次BFS，一次选择把全部边变成红色，另一次显然

然后一个点显然变两次是一样的，所以我们当边的颜色是否与当前选择的颜色不同给连接的点染色，若已染则判断是否相同或不同

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=1e5+10;;struct Edge {    int u,v,nx,type;}g[2*N];int cnt,list[N];int n,m; bool b[N],vis[N];int ok,ans=2147483647,lans[2];void Add(int u,int v,char type) {    g[++cnt]=(Edge){u,v,list[u],type=='R'?1:0};list[u]=cnt;    g[++cnt]=(Edge){v,u,list[v],type=='R'?1:0};list[v]=cnt;}int BFS(int v0,int same) {    queue
          
            q;    while (!q.empty()) q.pop();    q.push(v0);vis[v0]=1;    lans[1]++;    while (!q.empty()) {        int u=q.front();q.pop();        for (int i=list[u];i;i=g[i].nx) {            if (!vis[g[i].v]) {                b[g[i].v]=g[i].type==same?b[u]:(b[u]^1);                lans[b[u]^(g[i].type==same)]++;                q.push(g[i].v);                vis[g[i].v]=1;            }            else            if (g[i].type==same&&b[u]!=b[g[i].v]||g[i].type!=same&&b[u]==b[g[i].v]) return -1;        }    }    return min(lans[0],lans[1]);}int main() {    scanf("%d%d",&n,&m);    for (int i=1;i<=m;i++) {        int u,v;char c;        scanf("%d%d",&u,&v);        scanf("%c",&c);        while (c!='R'&&c!='B') scanf("%c",&c);        Add(u,v,c);    }    for (int i=0;i<2;i++) {        bool p=1;int cans=0,nans=0;        memset(b,0,sizeof b);memset(vis,0,sizeof vis);        for (int j=1;j<=n;j++) if (!vis[j]) {            lans[0]=lans[1]=0;            cans=BFS(j,i);            if (cans==-1) {                p=0;                break;            }            nans+=cans;        }        if (p) ans=min(ans,nans);        ok+=p;    }    if (!ok) printf("-1");    else printf("%d",ans);}