F - Domino Effect Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

あなたはドミノを並べています。

各 1 \leq i \leq N について「ドミノ S_i が倒れるとドミノ T_i が倒れる」という計 N 個の情報が与えられます。

与えられた情報から「ドミノ X を倒すとドミノ Y が倒れる」といえるか判定してください。

制約

  • 1 \leq N \leq 2\times 10^5
  • N は整数
  • S_i,T_i,X,Y は英小文字のみからなる長さ 1 以上 100 以下の文字列
  • X \neq Y
  • 全ての i で S_i \neq T_i
  • (S_i,T_i) は相異なる

入力

入力は以下の形式で標準入力から与えられる。

N
X Y
S_1 T_1
\vdots
S_N T_N

出力

与えられた情報から「ドミノ X を倒すとドミノ Y が倒れる」といえるとき Yes、いえないとき No と出力せよ。

入力例 1

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

出力例 1

Yes

2 番目の情報からドミノ second が倒れるとドミノ third が倒れること、3 番目の情報からドミノ 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

Problem Statement

You are lining up dominoes.

N clues are given: for each 1 \leq i \leq N, if domino S_i falls, then domino T_i will also fall.

Determine if the given clues imply that if domino X falls, then domino Y will also fall.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • N is an integer.
  • Each of S_i,T_i,X, and Y is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
  • X \neq Y
  • S_i \neq T_i for all i.
  • (S_i,T_i) are distinct.

Input

The input is given from Standard Input in the following format:

N
X Y
S_1 T_1
\vdots
S_N T_N

Output

Print Yes if the given clues imply that if domino X falls, then domino Y will also fall; print No otherwise.

Sample Input 1

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

Sample Output 1

Yes

The second clue states that if domino second falls, then domino third will also fall; and the third clue states that if domino third falls, then domino fourth will also fall.
Thus, we can infer that if domino second falls, then domino fourth will also fall.

Sample Input 2

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

Sample Output 2

No

One cannot infer from the given clues that if domino fourth falls, then domino second will also fall.

Sample Input 3

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

Sample Output 3

Yes

Sample Input 4

1
a b
x y

Sample Output 4

No