PRENDON - Prendonians

no tags 

The ancient civilization of the Prendonians, who lived in Jutland from 5000 BC to 4500 BC, is well known. A Prendonian name is composed of three non empty words formed by lowercase letters from a to z: an unique first name, one of their parents’ fist name with a suffix and the other parent’s name with the same suffix. The unique first name always comes first, but there is no specific order for the other two.

The suffix denotes the gender of the bearer of the name, jk for male and gvw for female, for example, if ric is igo and malte’s son, his full name would be ric igojk maltejk, but had ric been a girl, his name would have been ric igogvw maltegvw.

All the Prendonians were monogamic and faithful to their partners. There are no registers of male homosexual couples, but it was common for two women to be married, and there has not been a single case of married siblings in Prendonian history. A couple was not considered married until they had given birth to a child or adopted one.

Given N 3 word names, write a program that prints YES if they are all valid and part of a valid Prendonian family tree and everyone is related to everyone else, print NO otherwise.

Input

The first line consists of a single integer T (1 ≤ T ≤ 30), which is the number of test cases. Each test case begins with a line with only the integer N (1 ≤ N ≤ 1000), the number of names, followed by N lines with 3 word (a-z lowercase only, each word not longer than 103 characters), the first word is guaranteed to be unique.

Output

For each test case print YES if the names are all valid and part of a valid Prendonian family tree and are all related to each other, print NO otherwise.

Example

Input:
1
3
docs afegvw fegvw
draw rridajk cajk
pito docsjk drawjk

Output:
YES

hide comments
Ricardo Oliveira [UFPR]: 2012-02-20 18:27:54

You're checking (3) because "there are no registers of male homosexual couples", right?
Notice that, according the statement, "and there has not been a single case of married siblings in Prendonian history". The expressions are similar, so if you are checking (3), you have to check this other condition, too.

[Rampage] Blue.Mary: 2012-02-16 14:46:35

The sample is too weak. Most useful information is hidden in that (obscurity) English description.

Edit: I don't know if I've collected enough information. (I've got WA several times.) I assume that:

The first names in one test case will always be unique.

The answer to that test case is YES if and only if the following constraints is satisfied:

(1)The 2nd and 3rd names all end with "jk" (means that guy is male) or all end with "gvw" (means that guy is female). After deleting these suffixes, the names are his/her parents. These names can not be empty.
(2)One can not has children with more than one partner, or has children with him/herself.
(3)Two men can not get married.
(4)One can not give birth to his/her ancestors.
(5)Anyone is related to anyone else.

Edit: Finally I got Accepted. The next condition must be satisfied too:
(6)Two person with same parents can not get married.

Last edit: 2012-02-23 05:41:40

Added by:Paulo Costa
Date:2012-01-30
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFPR