String Equations

Time limit1sMemory limit128 MB

Summary

Decide whether a subset of distinct short strings and their repeats can be split into two groups whose multiset union of characters is identical.

Level: Medium7 of 10
Topics: Math, Number theory, Dynamic programming, Hash map
Solved: No attempts yet

Problem

We all understand numeric equations such as $3 + 8 = 4 + 7$ . But what happens if we work with strings instead of numbers? What would addition and equality mean?

Given two strings $x$ and $y$ , define $x + y$ to be the concatenation of the two strings. Define $x = y$ to mean that $x$ is an anagram of $y$ ; that is, the characters of $x$ can be rearranged to form $y$ .

You are given $n$ distinct non-empty strings, each consisting of at most $10$ lowercase letters. You may also assume that at most $10$ distinct characters appear across all of the strings. Decide whether you can place some strings on the left side and some strings on the right side of an equation so that the two "sums" are "equal" under the definitions above. Each string may be used $0$ or more times on a side, but no string may appear on both sides of the equation, and each side must use at least one string.

Input

The input contains several test cases. Each test case begins with a line containing the integer $n$ ( $2 \le n \le 100$ ). The next $n$ lines each contain one of the $n$ strings. The input terminates with a line containing $n = 0$ , which is not processed.

Output

For each test case, print a single line containing yes if it is possible to form such an equation, or no otherwise.

Examples7

Example 1

Input

2
hello
world
7
i
am
lord
voldemort
tom
marvolo
riddle
0

Expected output

no
yes

Example 2
Input
```
2
ab
ba
0
```
Expected output
```
yes
```
Example 3
Input
```
2
ab
cd
0
```
Expected output
```
no
```
Example 4
Input
```
3
a
b
ab
0
```
Expected output
```
yes
```
Example 5
Input
```
3
aa
ab
bb
0
```
Expected output
```
yes
```
Example 6
Input
```
3
a
b
c
0
```
Expected output
```
no
```

Example 7

Input

2
abc
cba
3
x
y
z
2
mango
tango
0

Expected output

yes
no
no