← 返回题目列表

AtCoder · past19_f

F. 多米诺骨牌倒塌

中文机器翻译题面 查看原题

问题陈述

你正在排列多米诺骨牌。

N 给出线索:对于每个 1 \leq i \leq N,如果多米诺骨牌 S_i 倒下,然后是多米诺骨牌 T_i 也会掉落。

确定给定的线索是否暗示如果多米诺骨牌 X 倒下,然后是多米诺骨牌 Y 也会掉落。

约束

  • 1 \leq N \leq 2\times 10^5
  • N 是一个整数。
  • 每个 S_i,T_i,X,和 Y 是长度介于 1 和 100,包含在内,由小写英文字母组成。
  • X \neq Y
  • S_i \neq T_i 对于所有人 i.
  • (S_i,T_i) 是不同的。

输入

输入由标准输入按以下格式给出:

N
X Y
S_1 T_1
\vdots
S_N T_N

输出

打印 Yes 如果给定的线索暗示如果多米诺骨牌 X 倒下,然后是多米诺骨牌 Y 也会掉落;打印 No 否则。


示例输入 1

5
second fourth
first second
second third
third fourth
fourth fifth
fifth sixth

示例输出 1

Yes

第二条线索指出,如果多米诺骨牌 second 倒下,然后是多米诺骨牌 third 也会掉落;第三条线索表明,如果多米诺骨牌 third 倒下,然后是多米诺骨牌 fourth 也会掉落。
因此,我们可以推断,如果多米诺骨牌 second 倒下,然后是多米诺骨牌 fourth 也会掉落。


示例输入 2

5
fourth second
first second
second third
third fourth
fourth fifth
fifth sixth

示例输出 2

No

人们无法从给定的线索推断出如果多米诺骨牌 每侧都有 fourth 倒下,然后是多米诺骨牌 second 也会掉落。


示例输入 3

6
e d
a b
b a
a c
c d
d e
e a

示例输出 3

Yes

示例输入 4

1
a b
x y

示例输出 4

No