Problem Description

There are $ N $ types of cards, each with $ 2019^{2019} $ copies.

The $ i $th type of card has a string $ A_i $ written on the top and a string $ B_i $ written on the bottom.

Consider selecting one or more of these cards and arranging them in any order. Let $ s $ be the concatenation of the strings written on the tops of the arranged cards, and let $ t $ be the concatenation of the strings written on the bottoms of the arranged cards.

Can you choose and arrange the cards to satisfy the following condition?

• Condition: It is possible to make $ s $ match $ t $ by deleting any number of characters (including zero) from any positions in $ s $.

Input Format

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $\vdots$ $ A_N $ $ B_N $

Output Format

Output YES if it is possible to choose and arrange the cards to satisfy the condition, otherwise output NO.

Sample Input and Output

Sample Input #1

2
cab ac
acba ab

Sample Output #1

YES

Sample Input #2

1
xmas contest

Sample Output #2

NO

Notes/Hints

Constraints

• $1 \leq N \leq 16$.
• $1 \leq |A_i|, |B_i| \leq 10^5$.
• $ A_i $ and $ B_i $ are strings consisting only of lowercase English letters.

Sample Explanation 1

For example, if you arrange the cards in the order of the 2nd type, 2nd type, and 1st type, then $ s = $acbaacbacab and $ t = $ababac, which satisfies the condition.

见题面 Input 部分

见题面 Output 部分