/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 7 点
問題文
英小文字の組 (a_1,b_1),(a_2,b_2),\dots,(a_N,b_N) があります。
英小文字 u,v が 似ている とは、(u,v)=(a_i,b_i) または (u,v)=(b_i,a_i) を満たす i が存在することを言います。
また、長さの等しい英小文字からなる文字列 U,V が 似ている とは、U,V が次の条件を満たすことを言います。
- U の文字を 1 つ選んで、似ている文字に置き換えることを好きなだけ繰り返したとき(操作をしなくてもよい)、V に一致させることができる。
長さの等しい文字列 S,T が与えらえるので、S と T が似ているか判定してください。
制約
- 1 \leq N \leq 325
- N は整数である。
- a_i,b_i は互いに異なる英小文字である。
- i \neq j ならば (a_i,b_i) \neq (a_j,b_j) かつ (a_i,b_i) \neq (b_j,a_j) が成り立つ。
- S,T は英小文字からなる長さ 1 以上 100 以下の文字列である。
- S の長さと T の長さは等しい。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 b_1 a_2 b_2 \vdots a_N b_N S T
出力
S と T が似ているならば Yes を、そうでないならば No を出力せよ。
入力例 1
1 m n man nan
出力例 1
Yes
S の 1 文字目を m から n に置き換えて nan にすることで、S を T と一致させることができます。m と n は似ている文字なので、S と T は似ている文字列の条件を満たします。
入力例 2
1 m n man men
出力例 2
No
入力例 3
3 a b a e d e abc edc
出力例 3
Yes
入力例 4
1 a b xyz xyz
出力例 4
Yes
Score : 7 points
Problem Statement
We have pairs of lowercase English letters (a_1,b_1),(a_2,b_2),\dots,(a_N,b_N).
Two lowercase English letters u and v are said to be similar if there exists i such that (u,v)=(a_i,b_i) or (u,v)=(b_i,a_i).
Two strings U and V with the same length are said to be similar if U and V satisfy the following condition:
- You can make U equal V by repeatedly (possibly zero times) choosing one of the characters of U and replacing it with a similar character.
Given strings S and T with the same length, determine if S and T are similar.
Constraints
- 1 \leq N \leq 325
- N is an integer.
- a_i and b_i are distinct lowercase English letters.
- If i \neq j, then (a_i,b_i) \neq (a_j,b_j) and (a_i,b_i) \neq (b_j,a_j).
- S and T are strings of length between 1 and 100, inclusive.
- S and T have the same length.
Input
Input is given from Standard Input in the following format:
N a_1 b_1 a_2 b_2 \vdots a_N b_N S T
Output
If S and T are similar, print Yes; otherwise, print No.
Sample Input 1
1 m n man nan
Sample Output 1
Yes
We can make S equal T by replacing the 1-st character of S with n, making S nan. Since m and n are similar characters, S and T satisfy the condition of similar strings.
Sample Input 2
1 m n man men
Sample Output 2
No
Sample Input 3
3 a b a e d e abc edc
Sample Output 3
Yes
Sample Input 4
1 a b xyz xyz
Sample Output 4
Yes