QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#802755#178. Three Kingdoms of Bourdelotcdx123456AC ✓88ms38632kbC++142.3kb2024-12-07 14:38:082024-12-07 14:38:10

Judging History

This is the latest submission verdict.

  • [2024-12-07 14:38:10]
  • Judged
  • Verdict: AC
  • Time: 88ms
  • Memory: 38632kb
  • [2024-12-07 14:38:08]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int n,tot,S,T,r[310],R[310],f[1010],g[310][310];
map<string,int> mp;
vector<int> a[310][310],v[310],v2[310];
vector<pair<int,int> > b[1010];
bool check(int x,int y){
	queue<int> q;
	memcpy(R,r,sizeof(r));
	for(int i=1;i<=tot;i++) v2[i]=v[i];
	v[x].push_back(y);
	r[y]++;
	for(int i=1;i<=tot;i++) if(!r[i]) q.push(i);
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(int i=0;i<v[x].size();i++){
			int y=v[x][i];
			r[y]--;
			if(!r[y]) q.push(y);
		}
	}
	int f=0;
	for(int i=1;i<=tot;i++) if(r[i]) f=1;
	memcpy(r,R,sizeof(r));
	for(int i=1;i<=tot;i++) v[i]=v2[i];
	return f;
}
int main(){
	ios::sync_with_stdio(0);
	string s;
	int x,y,z;
	cin>>s; if(!mp[s]) mp[s]=++tot; S=mp[s];
	cin>>s; if(!mp[s]) mp[s]=++tot; T=mp[s];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		for(int j=1;j<=x;j++){
			cin>>s; if(!mp[s]) mp[s]=++tot; y=mp[s];
			cin>>s; if(!mp[s]) mp[s]=++tot; z=mp[s];
			a[y][z].push_back(i);
			b[i].push_back(make_pair(y,z));
		}
	}
	queue<int> q;
	for(int i=0;i<a[S][T].size();i++) q.push(a[S][T][i]);
	while(1){
		int ff=0;
		while(!q.empty()){
			int x=q.front(); q.pop();
			if(f[x]) continue;
			f[x]=ff=1;
			for(int j=0;j<b[x].size();j++){
				int y=b[x][j].first,z=b[x][j].second;
				if(!g[y][z]){
					g[y][z]=1;
					v[y].push_back(z);
					r[z]++;	
				}
				for(int k=0;k<a[y][z].size();k++) q.push(a[y][z][k]);
			}
		}
		if(!ff) break;
		for(int k=1;k<=tot;k++){
			for(int i=1;i<=tot;i++){
				for(int j=1;j<=tot;j++){
					g[i][j]|=g[i][k]&g[k][j];
				}
			}
		}
		for(int i=1;i<=tot;i++){
			for(int j=1;j<=tot;j++){
				if(!g[i][j]) continue;
				for(int k=0;k<a[i][j].size();k++){
					q.push(a[i][j][k]);
				}
			}
		} 	
	}
	
	if(check(0,0)){
		cout<<"No";
		return 0;
	}
	
	for(int i=1;i<=tot;i++){
		for(int j=1;j<=tot;j++){
			if(i==j || g[i][j]) continue;
			if(g[j][i]){
				for(int k=0;k<a[i][j].size();k++){
					q.push(a[i][j][k]);
				}
			}
		}
	}
	while(!q.empty()){
		int x=q.front(); q.pop();
		if(f[x]==1){
			cout<<"No";
			return 0;
		}
		if(f[x]) continue;
		f[x]=2;
		for(int j=0;j<b[x].size();j++){
			int y=b[x][j].first,z=b[x][j].second;
			if(g[y][z]){
				cout<<"No";
				return 0;
			}
			for(int k=0;k<a[y][z].size();k++) q.push(a[y][z][k]);
		}
	}
	cout<<"Yes";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5876kb

input:

Alice Bob
3
2
Alice Bob
Bob Clare
2
Bob Clare
Clare David
2
Clare David
David Alice

output:

No

result:

ok single line: 'No'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5864kb

input:

Alice David
3
2
Alice Bob
Bob Clare
2
Bob Clare
Clare David
2
Clare David
David Alice

output:

Yes

result:

ok single line: 'Yes'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5936kb

input:

Alice Bob
1
2
Clare David
David Clare

output:

Yes

result:

ok single line: 'Yes'

Test #4:

score: 0
Accepted
time: 1ms
memory: 6136kb

input:

A B
2
2
A B
B D
3
B C
C D
B A

output:

Yes

result:

ok single line: 'Yes'

Test #5:

score: 0
Accepted
time: 1ms
memory: 6224kb

input:

a b
1
2
a b
b a

output:

No

result:

ok single line: 'No'

Test #6:

score: 0
Accepted
time: 1ms
memory: 6176kb

input:

a b
4
2
a b
c d
2
a b
d e
2
a b
c e
2
b a
c e

output:

No

result:

ok single line: 'No'

Test #7:

score: 0
Accepted
time: 1ms
memory: 6104kb

input:

a b
3
2
a b
c d
2
a b
d e
2
a b
e c

output:

No

result:

ok single line: 'No'

Test #8:

score: 0
Accepted
time: 0ms
memory: 6036kb

input:

a b
3
2
a b
c d
2
a b
d e
2
b a
e c

output:

Yes

result:

ok single line: 'Yes'

Test #9:

score: 0
Accepted
time: 0ms
memory: 6132kb

input:

a b
4
2
a b
b c
2
b c
c d
2
c d
d e
2
d e
e b

output:

No

result:

ok single line: 'No'

Test #10:

score: 0
Accepted
time: 69ms
memory: 6852kb

input:

qykf vqdy
677
2
dquh xn
ebzq dja
2
g blcab
rnoia s
2
ffaxo lfpcu
w qegx
12
yp qan
b w
zda te
tij eq
ea tk
ploh qg
xruto yp
qg vbz
dbtqi lqgja
cxk ygd
wb jvwg
j yp
8
l kgzg
gp i
haetc z
lqgja r
ixs yxc
v tjmr
ea lyb
q n
12
jzj hnngd
pq jzj
trhc fln
kzxa gbk
u al
jxq uxxch
id gbk
gcb tjs
ymyt llyy
oya...

output:

No

result:

ok single line: 'No'

Test #11:

score: 0
Accepted
time: 19ms
memory: 7764kb

input:

qykf vqdy
134
63
nzq d
prbwt nk
q azdaf
tk tij
qg ea
xruto ploh
qg vbz
lqgja ea
ygd dbtqi
jvwg cxk
qg wb
j qykf
s mbp
gzg z
ygd jvwg
i l
haetc gp
ea r
xruto yxc
tjmr ixs
v s
n lyb
j fhys
wg qykf
svnh i
ngdnj wg
cfl jyp
fg ztrh
m kakzx
xchqj lsuau
qaid yxc
gcb tjs
llyy nk
d ymyt
zshhf oyaw
atd qp
lqg...

output:

No

result:

ok single line: 'No'

Test #12:

score: 0
Accepted
time: 42ms
memory: 9812kb

input:

qykf vqdy
1000
14
tblca ebzq
mscrn w
ft i
qffax fpc
gxmwg zq
xtdhn lkh
yp qan
te b
eq zda
tk tij
ea ft
ploh qg
vbz xruto
dbtqi lqgja
59
q rm
n ybsj
fhys tblca
svnh wg
jyp ngdnj
ztrh cfl
kakzx fg
lsuau m
qaid xchqj
gcb tjs
ymyt llyy
zshhf oyaw
atd qp
bcag wg
nzvhk gob
xrl ebzq
tsa zl
tij oyaw
oaqbt f...

output:

No

result:

ok single line: 'No'

Test #13:

score: 0
Accepted
time: 27ms
memory: 6916kb

input:

jw wjtt
1000
56
cjo agi
ubyb kf
nali kf
ubyb nali
cjo u
fg cjo
fg fxei
ubyb u
agi u
kf fxei
fxei u
cjo ubyb
ubyb cjo
fxei nali
nali agi
u kf
agi cjo
fxei agi
kf nali
fxei fg
agi kf
fg u
agi ubyb
agi fxei
kf cjo
ubyb agi
cjo kf
fxei cjo
kf u
ubyb fg
cjo fg
agi fg
nali fxei
cjo fxei
fg kf
u cjo
nali f...

output:

No

result:

ok single line: 'No'

Test #14:

score: 0
Accepted
time: 5ms
memory: 6484kb

input:

qykf vqdy
314
93
qg ea
xruto ploh
lqgja vbz
ygd dbtqi
jvwg cxk
j wb
s mbp
gzg z
i l
haetc gp
r vqdy
ixs yxc
v tjmr
n lyb
s q
wg fhys
ea svnh
jyp ngdnj
ztrh cfl
kakzx fg
lsuau m
qaid xchqj
gcb tjs
ymyt llyy
oyaw m
zshhf fhys
atd qp
bcag kakzx
nzvhk gob
zl xrl
oaqbt tsa
mvkzg xamsd
xrl xchqj
l htzbf
h...

output:

Yes

result:

ok single line: 'Yes'

Test #15:

score: 0
Accepted
time: 66ms
memory: 10216kb

input:

qykf vqdy
6
33935
zm b
bpkfd ob
v vkman
bqcc qg
g zm
omn to
onva qmonv
xba er
ebjo yw
hvneu xttn
uxe xn
er esi
utc fhczo
l bkn
hgcno tifgc
zke yfck
wuxx gvjf
h yi
onva p
owg jfc
uk mmtip
j v
rrno xybcs
kxkxz q
aifrv wcd
mzvy hc
o awmp
i r
zxjge sznw
p m
wdyf qykf
ayrby qit
yi pumz
wwzuk uxe
uvba uai...

output:

No

result:

ok single line: 'No'

Test #16:

score: 0
Accepted
time: 48ms
memory: 9812kb

input:

qykf vqdy
1000
7
ydjae u
qmtbl b
w a
i mscrn
ft a
qffax fpc
gxmwg zq
51
w tojv
g zll
qi aidb
cxk ygd
wb jvwg
mbp j
z s
l gzg
haetc gp
ft r
ixs yxc
v tjmr
n lyb
fhys q
wg ixs
ngdnj svnh
jyp fpc
n cfl
fg ztrh
m kakzx
lsuau qmtbl
qaid xchqj
tjs cxk
gcb yxc
ymyt llyy
zshhf oyaw
atd qp
gob bcag
ygd nzvhk...

output:

No

result:

ok single line: 'No'

Test #17:

score: 0
Accepted
time: 60ms
memory: 9912kb

input:

qykf vqdy
7
4648
rfz qjhxz
jt xpri
dwz qn
pwdhn ygs
r i
z lqg
vu zi
e fpqv
s j
lfw dsen
pkdmx lm
qid cqyda
bqg tupcq
say jmz
xvdyk fpqv
jbay fv
qjhxz ff
xfbr xpn
y ow
fhr j
x ot
gyqm rzr
lzxu ygs
wjj wzsi
wzsi nv
cnyem n
fpqv gaenl
wtp xvdyk
uhdfu jxkgh
qtp l
uhdfu vbien
xfs lxxdh
dnj wlmif
d ztk
wz...

output:

No

result:

ok single line: 'No'

Test #18:

score: 0
Accepted
time: 63ms
memory: 10792kb

input:

nimu hmti
1000
250
g kw
mbtjo kw
xy kw
c smv
nbp n
jglw kw
ykef kw
xrpu kw
pjexm apxd
ssbkx kw
gzd kw
m kw
oe kw
uh kw
o kw
evc kw
god esh
ml kw
n kw
me kw
nsdx kw
atien kw
se llyvd
tzpu k
w kw
pzbch kw
ywxcl kw
yont kw
vcq kw
h lwknv
zh kw
yul kiskt
tfles kw
se kw
pjexm kw
xjhrs kw
pjexm zcww
hgy h...

output:

No

result:

ok single line: 'No'

Test #19:

score: 0
Accepted
time: 57ms
memory: 10900kb

input:

nimu hmti
1000
244
sakw ram
mbtjo g
xy ram
smv ram
c ram
n xy
nbp ram
ykef jglw
apxd xrpu
pjexm ram
ssbkx ram
gzd ram
m ram
uh oe
o ram
evc ram
god esh
ml ram
me ram
nsdx ram
atien ram
se llyvd
k ram
tzpu ram
w ram
pzbch ram
ywxcl ram
vcq yont
lwknv ram
h ram
zh ram
kiskt ram
tfles yul
xjhrs ram
apx...

output:

No

result:

ok single line: 'No'

Test #20:

score: 0
Accepted
time: 65ms
memory: 10880kb

input:

nimu hmti
1000
254
btjo a
smv xy
c a
n a
nbp a
jglw a
xrpu ykef
apxd a
pjexm a
ssbkx a
gzd a
m a
oe a
uh a
evc o
esh a
god a
ml a
me a
nsdx a
atien a
llyvd a
k se
w tzpu
pzbch a
ywxcl a
yont a
lwknv vcq
h a
zh a
kiskt a
yul a
ml tfles
k a
pjexm xjhrs
zcww a
hffv a
hgy a
b a
qw a
yj a
y augc
nimu a
r...

output:

No

result:

ok single line: 'No'

Test #21:

score: 0
Accepted
time: 57ms
memory: 10800kb

input:

nimu hmti
1000
247
ngam gsak
n tj
y tj
smv tj
nbp c
jglw tj
ykef tj
xrpu tj
pjexm apxd
ssbkx tj
gzd tj
m tj
uh oe
o tj
evc tj
esh tj
god tj
ml tj
me tj
nsdx tj
atien tj
se llyvd
k tj
tzpu tj
w tj
pzbch tj
ywxcl tj
yont tj
vcq w
lwknv tj
zh h
kiskt tj
yul tj
tfles tj
xjhrs tj
zcww tj
hffv tj
b hgy
qw...

output:

Yes

result:

ok single line: 'Yes'

Test #22:

score: 0
Accepted
time: 64ms
memory: 10820kb

input:

nimu hmti
1000
254
btjo a
xy a
smv a
c a
n a
jglw nbp
ykef a
xrpu a
apxd a
pjexm a
ssbkx a
gzd a
m a
oe a
uh a
o a
esh evc
god nbp
me ml
nsdx a
atien a
llyvd a
se a
k a
tzpu a
nbp w
pzbch a
yont ywxcl
lwknv vcq
h a
zh a
kiskt a
god yul
tfles a
apxd xjhrs
hffv zcww
se m
hgy a
b a
yj qw
augc a
y a
nim...

output:

No

result:

ok single line: 'No'

Test #23:

score: 0
Accepted
time: 62ms
memory: 10892kb

input:

nimu hmti
1000
239
vpr zo
m zo
sakw zo
g zo
mbtjo zo
xy zo
smv zo
n c
jglw nbp
ykef zo
apxd xrpu
pjexm zo
ssbkx zo
gzd zo
oe zo
uh zo
o zo
evc zo
esh zo
god zo
me ml
atien nsdx
llyvd zo
se zo
k zo
w tzpu
pzbch zo
yont ywxcl
vcq zo
h lwknv
zh zo
kiskt zo
yul zo
tfles zo
jglw zo
xjhrs zo
zcww zo
hffv ...

output:

Yes

result:

ok single line: 'Yes'

Test #24:

score: 0
Accepted
time: 59ms
memory: 10628kb

input:

nimu hmti
1000
229
fl ajy
rsu ajy
ot ajy
pr ajy
m ajy
sakw ajy
g ajy
mbtjo ajy
xy ajy
smv ajy
c ajy
n ajy
nbp ajy
jglw ajy
ykef ajy
xrpu ajy
apxd ajy
pjexm ajy
ssbkx ajy
gzd ajy
uh oe
o ajy
evc ajy
esh ajy
god ajy
me ml
atien nsdx
llyvd ajy
se ajy
k ajy
tzpu ajy
w ajy
pzbch ajy
ywxcl ajy
yont ajy
vc...

output:

No

result:

ok single line: 'No'

Test #25:

score: 0
Accepted
time: 56ms
memory: 10868kb

input:

nimu hmti
1000
242
m vpr
sakw vpr
g vpr
mbtjo vpr
xy vpr
smv vpr
c vpr
n vpr
jglw nbp
xrpu ykef
apxd vpr
pjexm vpr
ssbkx vpr
gzd vpr
xrpu vpr
oe vpr
o uh
evc apxd
esh vpr
god vpr
ml vpr
me vpr
nsdx vpr
atien vpr
se llyvd
tzpu k
w vpr
pzbch vpr
ywxcl vpr
k vpr
vcq yont
lwknv vpr
evc vpr
zh h
jglw vpr...

output:

No

result:

ok single line: 'No'

Test #26:

score: 0
Accepted
time: 85ms
memory: 6536kb

input:

qykf vqdy
1000
7
ydjae u
qmtbl b
w a
i mscrn
fpc ft
zq qffax
lkh gxmwg
1
qan xtdhn
1
te yp
6
tij q
ea tk
ploh qg
b tk
vbz xruto
dbtqi lqgja
3
xkuj dz
vbz wghw
bpks mjj
9
z gp
r haetc
yxc mscrn
tjmr ixs
ydjae v
j lyb
n v
fhys gp
ploh wg
15
dz u
u fln
gbk trhc
kzxa qmtbl
uxxch al
qykf w
id jxq
tjs n
x...

output:

No

result:

ok single line: 'No'

Test #27:

score: 0
Accepted
time: 47ms
memory: 8884kb

input:

qykf vqdy
1000
383
adwj it
ezmpp yl
kot tsraj
ho iolu
xnrt uie
au pw
u yl
to f
bjet i
rql n
xqt oio
m gj
xndhe ic
sl ycww
rnkrn h
a ezmpp
kmcv eew
rxu gvvk
laww oob
b cecy
kdmkb ywbr
sjb teiqr
rd paxyc
bh gqijs
on mw
wjfea xczm
yo uproh
fm mqijg
p btgc
ih jmbmt
xczm fnbk
ixen ftkfa
xczm xzxgb
eom uv...

output:

Yes

result:

ok single line: 'Yes'

Test #28:

score: 0
Accepted
time: 46ms
memory: 9280kb

input:

qykf vqdy
988
107
zll tojv
aidb g
ygd qi
jvwg cxk
j wb
s mbp
gzg z
i l
haetc gp
yxc r
gzg ixs
v tjmr
n lyb
fhys q
svnh wg
jyp ngdnj
ztrh cfl
fg wb
m kakzx
ngdnj lsuau
xchqj haetc
tjs qaid
v gcb
ymyt llyy
zshhf oyaw
qp cfl
bcag atd
gob m
xrl nzvhk
tsa zl
xamsd oaqbt
qykf mvkzg
qi htzbf
t vglv
gz wszx...

output:

No

result:

ok single line: 'No'

Test #29:

score: 0
Accepted
time: 77ms
memory: 10340kb

input:

qykf vqdy
1000
169
cs clrcy
mrmvq xsut
i ybsj
q n
wg fhys
ngdnj svnh
cfl jyp
fg ztrh
m kakzx
xchqj lsuau
tjs qaid
llyy gcb
oyaw ymyt
zshhf qykf
atd qp
gob bcag
xrl nzvhk
zl ybsj
oaqbt tsa
vqdy xamsd
mvkzg ybsj
vglv htzbf
wszxf t
bjm gz
mjymx cfd
zs bd
dwja tv
p liez
bcag atsr
otqi ju
uie luaho
kakzx...

output:

No

result:

ok single line: 'No'

Test #30:

score: 0
Accepted
time: 68ms
memory: 9992kb

input:

qykf vqdy
909
54
glk w
zqank vxtdh
azdaf prbwt
tij q
ea tk
ploh qg
vbz xruto
dbtqi lqgja
cxk ygd
wb jvwg
mbp j
z s
gzg w
tij l
ygd i
w gp
r haetc
ixs yxc
v tjmr
q lyb
fhys n
svnh wg
jyp ngdnj
ztrh cfl
kakzx fg
lsuau m
qaid xchqj
gcb tjs
ymyt llyy
zshhf oyaw
atd qp
bcag r
nzvhk gob
zl xrl
vxtdh tsa
x...

output:

No

result:

ok single line: 'No'

Test #31:

score: 0
Accepted
time: 65ms
memory: 10284kb

input:

qykf vqdy
255
508
oob xu
it laww
b cecy
kdmkb ywbr
sjb teiqr
rd paxyc
bh gqijs
on mw
n xczm
uproh wjfea
u yo
fm mqijg
p btgc
ih jmbmt
ftkfa fnbk
xzxgb ixen
eom uvaot
dbz qro
vk cuk
ylffo lm
llf bzth
trnns bbzt
cg eexm
aoxey dcbr
mofi ihb
kg f
jyyl g
e sas
zitp tvvj
v lk
uobsp qfyl
cu ihb
hqb qvrl
ww...

output:

No

result:

ok single line: 'No'

Test #32:

score: 0
Accepted
time: 86ms
memory: 10288kb

input:

qykf vqdy
665
229
gbk rhc
al kzxa
uxxch u
id jxq
gcb tjs
ymyt llyy
zshhf oyaw
atd qp
gob bcag
xrl nzvhk
m jxq
tsa zl
xamsd oaqbt
htzbf mvkzg
t vglv
gz wszxf
cfd bjm
bd mjymx
tv zs
tjs dwja
p liez
ju atsr
luaho otqi
xnrt uie
pw cfd
f au
i to
n bjet
rql uxxch
xqt oio
atsr gj
ic gz
xndhe ymyt
sl ycww
h...

output:

No

result:

ok single line: 'No'

Test #33:

score: 0
Accepted
time: 82ms
memory: 10216kb

input:

qykf vqdy
467
21
bwgms lc
tl rnoia
u p
qegx ffaxo
glk w
zqank vxtdh
azdaf prbwt
tij q
ea tk
ploh qg
zqank xruto
lqgja vbz
ygd dbtqi
cxk azdaf
wb jvwg
j vxtdh
s mbp
gzg z
xruto l
gp i
azdaf haetc
97
cxk ullyy
oyaw ymyt
qp zshhf
bcag atd
nzvhk gob
m xrl
tsa zl
xamsd oaqbt
htzbf mvkzg
t vglv
gz wszxf
c...

output:

No

result:

ok single line: 'No'

Test #34:

score: 0
Accepted
time: 57ms
memory: 7344kb

input:

qykf vqdy
1000
22
g cab
rnoia s
p tl
ffaxo u
w qegx
vxtdh glk
prbwt zqank
q azdaf
tk tij
qg ea
ploh g
q xruto
lqgja vbz
ygd dbtqi
jvwg cxk
j wb
z mbp
l gzg
zqank i
haetc gp
yxc r
tjmr ixs
28
jyp ngdnj
ztrh cfl
ploh fg
m kakzx
xchqj lsuau
tjs qaid
gcb gp
ymyt llyy
oyaw lqgja
qp zshhf
atd jvwg
gob bca...

output:

No

result:

ok single line: 'No'

Test #35:

score: 0
Accepted
time: 82ms
memory: 10472kb

input:

qykf vqdy
670
12
zqmt aee
bwgms lc
tl rnoia
u p
ffaxo u
w qegx
vxtdh glk
zqank tl
azdaf prbwt
tij q
ea tk
ploh qg
153
tjs aid
gcb w
ymyt llyy
zshhf oyaw
atd qp
gob bcag
vqdy nzvhk
m xrl
tsa zl
oaqbt vqdy
mvkzg xamsd
llyy htzbf
t vglv
gz wszxf
cfd bjm
bd mjymx
ea zs
dwja tv
vqdy liez
ju atsr
luaho ot...

output:

No

result:

ok single line: 'No'

Test #36:

score: 0
Accepted
time: 80ms
memory: 10440kb

input:

qykf vqdy
960
195
f h
wg yfhys
ngdnj svnh
cfl jyp
fg ztrh
m kakzx
xchqj lsuau
tjs qaid
llyy gcb
oyaw ymyt
qp zshhf
bcag atd
nzvhk gob
zl xrl
oaqbt tsa
mvkzg xamsd
vglv htzbf
wszxf t
bjm gz
mjymx cfd
zs bd
h tv
liez dwja
atsr p
lsuau t
ju lsuau
luaho otqi
uie tsa
pw xnrt
u au
i to
luaho bjet
rql n
oi...

output:

No

result:

ok single line: 'No'

Test #37:

score: 0
Accepted
time: 42ms
memory: 9216kb

input:

qykf vqdy
1000
21
bwgms lc
tl rnoia
u p
qegx ffaxo
glk w
zqank vxtdh
azdaf prbwt
tij q
ea tk
ploh qg
vbz xruto
dbtqi lqgja
tl ygd
jvwg cxk
tl wb
j ygd
s mbp
gzg z
i l
haetc gp
yxc r
32
ngdnj svnh
cfl jyp
prbwt ztrh
kakzx fg
lsuau m
qaid xchqj
tjs xchqj
kakzx gcb
ymyt llyy
zshhf oyaw
rnoia qp
lsuau a...

output:

Yes

result:

ok single line: 'Yes'

Test #38:

score: 0
Accepted
time: 88ms
memory: 10356kb

input:

qykf vqdy
648
72
azdaf prbwt
tij q
ea tk
ploh qg
vbz xruto
dbtqi lqgja
cxk ygd
wb jvwg
mbp j
xruto s
gzg z
i l
haetc gp
ploh r
cxk yxc
tjmr ixs
tk v
lyb v
fhys n
wg qg
ngdnj svnh
cfl jyp
fg ztrh
v yxc
kakzx ploh
tk m
xchqj lsuau
tjs qaid
gcb lyb
ymyt llyy
zshhf oyaw
atd qp
gob bcag
xrl nzvhk
zl jvwg...

output:

No

result:

ok single line: 'No'

Test #39:

score: 0
Accepted
time: 38ms
memory: 6908kb

input:

hpfn mbmte
1000
6
mz ua
qdfsy i
ojl blipi
mjh npn
ahvv hg
agb bvomg
3
op j
aw nc
msfhr t
30
v g
xgdk agb
xgdk prgrc
q rlzv
iaobr amyi
msfhr mjh
en qyf
byuva cjwxy
xs wfxd
rzjly ccscq
e aza
dr wbfzh
hbn qqb
kyvon x
zzgws nfki
qyf en
hbn ve
irbhi f
yj zamz
zxr awubg
xska rkqpy
xdbda t
z hg
nxok l
mmgd...

output:

No

result:

ok single line: 'No'

Test #40:

score: 0
Accepted
time: 27ms
memory: 8080kb

input:

qiu bz
298
118
y vkj
rrok vkj
t vkj
czdx vkj
q vkj
obv vkj
zuebj vkj
uxib vkj
hdj vkj
pwjrv vkj
qxn vkj
yw vkj
uzvz vkj
bbhvt vkj
l vkj
rfqfp vkj
ci vkj
nmq vkj
prqom vkj
zajpa vkj
kfi vkj
kci vkj
wzx vkj
lbazh fj
lbazh vkj
df vkj
qwdof vkj
zcn vkj
g vkj
rlbts vkj
ogny vkj
grhb vkj
tzpcm vkj
sv vkj
...

output:

Yes

result:

ok single line: 'Yes'

Test #41:

score: 0
Accepted
time: 35ms
memory: 8700kb

input:

qiu bz
298
145
bohd bjfux
ipw bjfux
rvxqx bjfux
gyw bjfux
uzvz bjfux
bbhvt bjfux
l bjfux
rfqfp bjfux
ci bjfux
nmq bjfux
prqom bjfux
zajpa bjfux
kfi bjfux
kci bjfux
wzx bjfux
fj bjfux
lbazh bjfux
df bjfux
qwdof bjfux
zcn bjfux
g bjfux
rlbts bjfux
ogny bjfux
tzpcm grhb
tzpcm bjfux
sv bjfux
yj bjfux
pm...

output:

No

result:

ok single line: 'No'

Test #42:

score: 0
Accepted
time: 50ms
memory: 14272kb

input:

al xa
1000
14
ongtp lx
t xjkk
jrkl sdmme
xjkk ggc
weba al
gjjt c
xa al
cy weba
mo sdb
lb qmcc
fsfjk ggc
bj omht
oyo zlk
b xa
69
gn uteki
wdq xtw
cw qmaq
pbx omht
ycfr w
jedti rg
locyx yhwp
eu ti
gjoxi j
hxgqh quf
j n
vzrwn zpfq
sknp g
mwqh pmin
il ti
fftor cl
sdb ckxmy
jgjm jl
vap dgxr
wghxu pkrfj
d...

output:

Yes

result:

ok single line: 'Yes'

Test #43:

score: 0
Accepted
time: 34ms
memory: 8544kb

input:

qiu bz
298
138
zuebj obv
uxib obv
hdj obv
pwjrv obv
qxn obv
yw obv
uzvz obv
bbhvt obv
l obv
rfqfp obv
ci obv
nmq obv
prqom obv
zajpa obv
kfi obv
kci obv
wzx obv
fj obv
lbazh obv
df obv
qwdof obv
zcn obv
g obv
ogny rlbts
ogny obv
grhb obv
tzpcm obv
sv obv
yj obv
pmv obv
zhbbg obv
hzzu obv
apd obv
bb ...

output:

No

result:

ok single line: 'No'

Test #44:

score: 0
Accepted
time: 30ms
memory: 8932kb

input:

qiu bz
298
145
bohd bjfux
ipw bjfux
rvxqx bjfux
gyw bjfux
uzvz bjfux
bbhvt bjfux
l bjfux
rfqfp bjfux
ci bjfux
nmq bjfux
prqom bjfux
zajpa bjfux
kfi bjfux
kci bjfux
wzx bjfux
fj bjfux
lbazh bjfux
df bjfux
qwdof bjfux
zcn bjfux
g bjfux
rlbts bjfux
ogny bjfux
tzpcm grhb
tzpcm bjfux
sv bjfux
yj bjfux
pm...

output:

Yes

result:

ok single line: 'Yes'

Test #45:

score: 0
Accepted
time: 73ms
memory: 10448kb

input:

r f
1000
648
q ztn
bhbtb smnr
q kkyd
j xrqxg
g gl
g qiwsj
etuya p
wku fln
k mim
spr ax
fln rxa
zps braa
gf do
pvy owidl
lzar xrqxg
lh c
o fxyar
tg xwnmc
bbhby hsnry
xrqxg uqn
b ttwuq
w kqm
pmcvj zps
ha iwvi
xa kqm
hkcdc nf
lh owidl
ijsqu gyo
lrom ztn
imr yvzvy
rxa nmexy
bur j
azgu lzar
dt vh
smnr fn...

output:

No

result:

ok single line: 'No'

Test #46:

score: 0
Accepted
time: 19ms
memory: 6948kb

input:

qiu bz
298
37
ccs khyhi
vqd khyhi
n khyhi
sahtd khyhi
hj khyhi
zxqif khyhi
vpvdr khyhi
ofipf khyhi
lwgo khyhi
yyl khyhi
c khyhi
fk khyhi
ng khyhi
i khyhi
zrixw khyhi
ifc khyhi
ylsqm khyhi
flkv khyhi
jgyor khyhi
okst khyhi
czdx khyhi
q khyhi
obv khyhi
zuebj ng
zuebj khyhi
uxib khyhi
hdj khyhi
pwjrv k...

output:

Yes

result:

ok single line: 'Yes'

Test #47:

score: 0
Accepted
time: 43ms
memory: 7060kb

input:

wmwx hvjwe
1000
21
h ujbhe
v qf
r rvirf
lyb jcqfn
icoyz ieac
nwd i
nk dbwxs
nk wmwx
z pp
ofa nk
ckdf u
af wmwx
qae lxq
w lbg
kjs pdl
o nrh
j nrh
mzwi ka
l zacxl
urlm q
dbwxs vx
12
dbwxs vx
af dbwxs
qf wbxer
vx hvjwe
nrh wmwx
bill dbwxs
ptecy hngtu
kez wmo
mykhp nk
osqvg knoy
ptecy kez
lw yh
39
zzh p...

output:

No

result:

ok single line: 'No'

Test #48:

score: 0
Accepted
time: 22ms
memory: 7060kb

input:

pkw kdv
1000
11
qzcss ojgth
db r
gtroh ce
xmz neqs
s htt
dw e
ut ssw
d nwdf
k uf
tndu qfil
qzcss nwdf
49
t sj
b sj
w sj
pxv sj
rxoz sj
yzd sj
wpg sj
yyaw sj
hvr sj
riim sj
dsez sj
kuubz sj
ojgth sj
g sj
l sj
ts sj
ho sj
qfil sj
dvfw sj
urayi sj
iqjjx sj
xb sj
mu sj
ucas sj
rybu sj
d sj
qzcss sj
jm s...

output:

Yes

result:

ok single line: 'Yes'

Test #49:

score: 0
Accepted
time: 38ms
memory: 8116kb

input:

ew ciuk
1000
76
rto o
pq kh
rgruv yjta
dvput ek
p jdtz
cgh xg
pys gj
n fhod
ncoo vu
kxgan fiw
wvll heyu
cnfe izdq
rgruv wvll
xsxn fur
u hmkih
dn imet
xhsr az
ujknu psjj
cdxpf izdq
dn rhrp
l izkzd
rhrp dn
sa msbr
fiw tf
evvna wevl
izdq u
zdf izkzd
usqn zup
uf bg
sb risfu
msxwf omv
x twh
pjy dp
y au
d...

output:

Yes

result:

ok single line: 'Yes'

Test #50:

score: 0
Accepted
time: 35ms
memory: 8732kb

input:

qiu bz
298
145
bohd bjfux
ipw bjfux
rvxqx bjfux
gyw bjfux
uzvz bjfux
bbhvt bjfux
l bjfux
rfqfp bjfux
ci bjfux
nmq bjfux
prqom bjfux
zajpa bjfux
kfi bjfux
kci bjfux
wzx bjfux
fj bjfux
lbazh bjfux
df bjfux
qwdof bjfux
zcn bjfux
g bjfux
rlbts bjfux
ogny bjfux
tzpcm grhb
tzpcm bjfux
sv bjfux
yj bjfux
pm...

output:

No

result:

ok single line: 'No'

Test #51:

score: 0
Accepted
time: 49ms
memory: 9200kb

input:

txal eux
1000
235
qtfk s
b s
mzqcr s
u s
hc s
lv s
rk s
xuh s
sy s
uhyy s
pbqzu s
m s
imfmc s
iunny s
qtzqt s
w s
wwi s
tokf s
pzw s
myx s
fbs s
evgd s
lxd s
lrl s
x s
eb s
sd s
nymr s
ml s
plugn s
snanv s
bow s
mgi s
nvkq s
r s
qjkhx s
tnr s
ljkhx s
emrxh s
uv s
hezkv s
g s
jqtlh s
vdqqk s
qnt s
l ...

output:

Yes

result:

ok single line: 'Yes'

Test #52:

score: 0
Accepted
time: 59ms
memory: 10956kb

input:

dv drzi
1000
14
kts h
uwh vwmn
ww f
j src
q fjuld
xhja eocms
h cnjpu
ww m
ke cd
haqpd eocms
cxu yc
vwmn dlwsz
jwfja okmx
iluz l
17
ycdb hcpt
cuhhq hcpt
m hcpt
y hcpt
dv hcpt
yiwsf hcpt
eocms hcpt
awelj hcpt
szwp hcpt
c hcpt
qav hcpt
tqr hcpt
uhcu hcpt
ntdig hcpt
drzi hcpt
p hcpt
eocms y
20
nmnm uq
q...

output:

No

result:

ok single line: 'No'

Test #53:

score: 0
Accepted
time: 72ms
memory: 38632kb

input:

dzmpm tj
1000
121
uinz hjytd
ir guxj
hjytd qfevb
fs ie
dxdvc mzkm
ieg vhq
qek medv
ieg pda
m xqlqe
xrx vv
hjytd mzioa
ieg qfevb
nffup pda
vzb vgvia
hjytd qek
t booxw
df ezng
qfevb pda
medv qfevb
i wllgh
medv mzioa
ozzg cu
sbuku hhobf
pda nffup
n oaa
qfevb nffup
myd nffup
myd medv
myd qfevb
ieg guxj
...

output:

Yes

result:

ok single line: 'Yes'

Test #54:

score: 0
Accepted
time: 55ms
memory: 8596kb

input:

rudrr w
1000
101
ci tspbq
jaofe uk
lgcno nfqq
c u
dqpm wg
y ovk
ij ocmd
iyqfp nre
wh vhaqf
b dm
wh ovk
afs y
cbbic djcx
nnc ilxp
rw tjlqj
jyf yb
szl mg
djc wlgv
zd n
nnc mg
jd dvf
kiul wcdry
h qz
dprp wlgv
ja ooi
rddz xn
mce xer
tjlqj bvb
u nnc
oz btju
cns vrem
l ooi
r io
vvhfa izs
hiid zd
srnoc qca...

output:

Yes

result:

ok single line: 'Yes'

Test #55:

score: 0
Accepted
time: 52ms
memory: 8008kb

input:

qdj pqas
1000
24
djfy uufcu
agcg jj
az ih
rods znkq
l zrw
d c
qzpzq ltvim
agcg h
q c
pgs w
w sde
sde vxu
ehyj xoifp
ih h
ej e
pgs fcoi
r yks
pgva jbdnq
rlxk ew
pgva gxi
xhxv yk
ucxw mlt
ghim iqa
aoe sde
46
pgva xhxv
xqse qfs
jbdnq mm
d cqqes
ghim wn
uch ih
use oqh
cqqes qfs
fzrg xg
huv x
mlnp gk
dog...

output:

No

result:

ok single line: 'No'

Test #56:

score: 0
Accepted
time: 35ms
memory: 8696kb

input:

qiu bz
298
145
bohd bjfux
ipw bjfux
rvxqx bjfux
gyw bjfux
uzvz bjfux
bbhvt bjfux
l bjfux
rfqfp bjfux
ci bjfux
nmq bjfux
prqom bjfux
zajpa bjfux
kfi bjfux
kci bjfux
wzx bjfux
fj bjfux
lbazh bjfux
df bjfux
qwdof bjfux
zcn bjfux
g bjfux
rlbts bjfux
ogny bjfux
tzpcm grhb
tzpcm bjfux
sv bjfux
yj bjfux
pm...

output:

Yes

result:

ok single line: 'Yes'

Test #57:

score: 0
Accepted
time: 27ms
memory: 7528kb

input:

qiu bz
298
83
c osyyl
fk osyyl
ng osyyl
i osyyl
zrixw osyyl
ifc osyyl
ylsqm osyyl
flkv osyyl
jgyor osyyl
okst osyyl
czdx osyyl
q osyyl
obv osyyl
zuebj osyyl
uxib osyyl
hdj osyyl
pwjrv osyyl
qxn osyyl
yw osyyl
uzvz osyyl
bbhvt osyyl
l osyyl
rfqfp osyyl
nmq ci
nmq osyyl
prqom osyyl
zajpa osyyl
kfi osy...

output:

No

result:

ok single line: 'No'

Test #58:

score: 0
Accepted
time: 47ms
memory: 8828kb

input:

usju jircq
1000
125
szs xe
l ps
n inw
c a
ky s
g k
to ocxga
nr gain
m tx
owm iflhl
u dqyqf
rvtaq mrrxw
ggbnn vaeoh
c v
mrrxw wpnd
fljdf lqgpv
lgpjx u
orots njxeb
njxeb csbk
opvcm p
nr bfz
ucl eejst
ucl dqyqf
ftozt szs
jv sz
ruc kjo
taf njxeb
gain rvtaq
ah v
gcrj vde
s cz
jv ucl
zq owm
gcrj to
eoode ...

output:

Yes

result:

ok single line: 'Yes'

Test #59:

score: 0
Accepted
time: 1ms
memory: 6092kb

input:

A B
3
3
A B
B C
D E
2
A C
C D
2
C E
E A

output:

No

result:

ok single line: 'No'