It's Raining, Man

Interview

Time limit2sMemory limit512 MB

Summary

Given a set of distinct cards, decide whether they can be ordered in a row so that each neighbouring pair shares a rank or a suit.

Level: Medium5 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

Walter is spending the holidays on his great-grandfather's farm. It has been raining for days. Sitting in the attic of an aged barn and digging through piles of dusty junk, Walter finds a bunch of old poker cards. The cards look antique and interesting, so he starts to lay them down one by one, side by side, on the floor. Then he notices that there is some order in the sequence: many pairs of neighbouring cards are either of the same rank or of the same suit.

"This might be a nice little puzzle," Walter says to himself. "Can I rearrange the cards so that every two neighbouring cards share the rank or the suit? But the bunch is incomplete, and that might cut down the possible arrangements badly."

You are given the cards Walter found. Decide whether all of them can be laid out in one row so that every two neighbouring cards have the same rank or the same suit.

Input

The input holds several test cases. Each test case is a single line that lists every card in the bunch. The line starts with the number of cards $1 \le L \le 52$ , followed by $L$ card descriptions separated by single spaces.

A card is written with two characters. The first character is the rank, where A is the ace, 2 to 9 are those numbers, X is 10, J is the jack, Q is the queen and K is the king. The second character is the suit, where C is clubs, D is diamonds, H is hearts and S is spades.

All cards inside one test case are different. The input holds at most 100 test cases and ends at the end of the file.

Output

For each test case print one line: YES if the cards can be laid out as required, NO otherwise.

Examples4

Example 1

Input

8 2C 2D 2H 2S XC JS QS KS
4 5C 4H AS 9D

Expected output

YES
NO

Example 2

Input

1 AC
2 AC 2D
2 AC AD
2 AC 2C

Expected output

YES
NO
YES
YES

Example 3
Input
```
6 AC AD 2C 2H 3C 3S
```
Expected output
```
NO
```

Example 4

Input

52 AC AD AH AS 2C 2D 2H 2S 3C 3D 3H 3S 4C 4D 4H 4S 5C 5D 5H 5S 6C 6D 6H 6S 7C 7D 7H 7S 8C 8D 8H 8S 9C 9D 9H 9S XC XD XH XS JC JD JH JS QC QD QH QS KC KD KH KS

Expected output

YES