1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
| #include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define rep(i,__l,__r) for(signed i=(__l),i##_end_=(__r);i<=i##_end_;++i)
#define fep(i,__l,__r) for(signed i=(__l),i##_end_=(__r);i>=i##_end_;--i)
#define erep(i,u) for(signed i=tail[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
typedef long long LL;
// typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef unsigned uint;
#define Endl putchar('\n')
// #define int long long
// #define int unsigned
// #define int unsigned long long
#define cg (c=getchar())
template<class T>inline void read(T& x){
char c;bool f=0;
while(cg<'0'||'9'<c)f|=(c=='-');
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
template<class T>inline T read(const T sample){
T x=0;char c;bool f=0;
while(cg<'0'||'9'<c)f|=(c=='-');
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
template<class T>void fwrit(const T x){//just short,int and long long
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>9)fwrit(x/10);
putchar(x%10^48);
}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline int gcd(const int a,const int b){return b?gcd(b,a%b):a;}
inline void getInv(int inv[],const int lim,const int MOD){
inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
inline LL mulMod(const LL a,const LL b,const LL mod){//long long multiplie_mod
return ((a*b-(LL)((long double)a/mod*b+1e-8)*mod)%mod+mod)%mod;
}
const int MAXN=100000;
const int MAXM=100000;
const int INF=(1<<30)-1;
struct edge{int to,nxt,c;}e[MAXM*2+5];
int tail[MAXN+5],ecnt;
inline void add_edge(const int u,const int v,const int c){
e[++ecnt]=edge{v,tail[u],c};tail[u]=ecnt;
e[++ecnt]=edge{u,tail[v],c};tail[v]=ecnt;
}
int n,m;
inline void Init(){
n=read(1),m=read(1);
int u,v;char ch[5];
rep(i,1,m){
scanf("%d %d %s",&u,&v,ch);
add_edge(u,v,ch[0]=='R');
}
}
int rever[MAXN+5];
void Clear(const int u){
rever[u]=-1;
for(int i=tail[u];i;i=e[i].nxt)if(rever[e[i].to]!=-1)
Clear(e[i].to);
}
int Judge(const int u,const int rev,const int goal){
int sum=rev,ret;
rever[u]=rev;
for(int i=tail[u],v,tore;i;i=e[i].nxt){
v=e[i].to;
tore=goal^e[i].c^rev;
if(rever[v]!=-1 && rever[v]!=tore)return -1;
if(rever[v]==-1){
ret=Judge(v,tore,goal);
if(ret==-1)return -1;
sum+=ret;
}
}return sum;
}
int ans=INF,memo[MAXN+5];
signed main(){
Init();
int ans1,ans2,f1,f2;
bool flg;
rep(t,0,1){//枚举颜色
flg=false;
memset(rever,-1,sizeof rever);
rep(i,1,n)if(rever[i]==-1){
Clear(i),ans1=Judge(i,0,t);
Clear(i),ans2=Judge(i,1,t);
// printf("When i == %d, ans1 == %d, ans2 == %d\n",i,ans1,ans2);
if(ans1==-1 && ans2==-1){flg=true;break;}
if(ans2==-1 || ans1<ans2){
Clear(i);
Judge(i,0,t);
}
}
if(!flg){
int tot=0;
rep(i,1,n)if(rever[i]==1)++tot;
if(tot>(n/2)){
tot=n-tot;
rep(i,1,n)rever[i]=!rever[i];
}
if(tot<ans){
ans=tot;
rep(i,1,n)memo[i]=rever[i];
}
}
}
if(ans==INF)puts("-1");
else{
writc(ans,'\n');
rep(i,1,n)if(memo[i])writc(i,' ');Endl;
}
return 0;
}
/*
6 6
1 2 R
1 3 R
2 3 R
4 5 B
4 6 B
5 6 B
ans == -1
*/
|
) providing the initial color of this edge. If $ c_{i} $ equals ‘R’, then this edge is initially colored red. Otherwise, $ c_{i} $ is equal to ‘B’ and this edge is initially colored blue. It’s guaranteed that there are no self-loops and multiple edges.