Fix-Free Check

Interview

Time limit1sMemory limit128 MB

Summary

For each triple of words, decide whether no word is a prefix or suffix of another, printing Yes or No.

Level: Easy3 of 10
Topics: String, Brute force, Implementation, Sorting
Solved: No attempts yet

Problem

A collection of words is prefix-free if no word is a prefix of any other word. A collection of words is suffix-free if no word is a suffix of any other word. A collection of words is fix-free if it is both prefix-free and suffix-free.

In this problem, a word is a sequence of lower-case letters whose length is between $1$ and $25$ . A word $X$ is a prefix of a word $Y$ if, for some $n$ , $X$ consists of the first $n$ characters of $Y$ in order. For example, the prefixes of the word cat are c, ca, and cat. Similarly, a word $X$ is a suffix of $Y$ if $X$ consists of the last $n$ characters of $Y$ in order.

Input

The first line contains the number of collections $N$ . The following $3N$ lines describe the $N$ collections in order, with three words per collection and one word per line. That is, lines $2$ , $3$ , and $4$ form the first collection, lines $5$ , $6$ , and $7$ form the second collection, and so on.

Output

For each collection, print one line containing Yes if that collection is fix-free, or No otherwise. Print $N$ lines in the order the collections are given.

Examples3

Example 1
Input
```
2
abba
aab
bab
a
ab
aa
```
Expected output
```
Yes
No
```
Example 2
Input
```
1
cat
at
dog
```
Expected output
```
No
```
Example 3
Input
```
1
abc
bca
cab
```
Expected output
```
Yes
```