You Might be a Redneck

After proving his "intelligence" to Billy-Bob, Jim-Bob decides to give him a puzzle. He describes his family tree to Billy-Bob and asks him, "Am I a redneck?"

Jim-Bob's family consists of N (1 ≤ N ≤ 1000) people, including himself. Person i has a name ni with no spaces in it. They also have pi (0 ≤ pi ≤ 2) parents (sometimes Jim-Bob can only remember one or neither of a person's parents). A person can never be his/her own parent. Though Jim-Bob calls it his family tree, it's more like just a collection of people he knows, some people might not be related in any way to other people.

A good way to identify a redneck is by a strange family structure (for example, if their daughter is also their mother). If for any family member, one of their direct ancestors (parents, grandparents, etc.) is also one of their direct descendants (children, grandchildren, etc.), then that person is a redneck. If Jim-Bob is in any way related to a redneck, then he himself might be a redneck.

Now, Billy-Bob also isn't too bright, so he asks you to help him figure it out. Given T (1 ≤ T ≤ 5) cases of Jim-Bob's family tree, determine whether or not he might be a redneck.


A single integer — T.
For each case:
A single integer — N.
The next N lines each contain information about a person — a string ni, an integer pi, and then pi names (the names of person i's parents, each of which will be one of the N people).


For each case, simply output "Redneck" or "Not a redneck", depending on whether or not Jim-Bob is related to any rednecks.

Sample Input

Jim-Bob 0
Mary-Ann 0
John 1 Matt
Bob-Jim 2 Jim-Bob Mary-Ann
Tina 1 John
Matt 1 Tina

Sample Output

Not a redneck


John is a redneck, since Matt is his father and also his grandson. This also applies to Matt and Tina.
However, Jim-Bob is not related to any of them, and his own family is quite normal (he and Mary-Ann have a son, Bob-Jim). Therefore, Jim-Bob is definitely not a redneck.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 17, 2008
Author: SourSpinach

Languages Allowed:

Comments (Search)

what is the largest length of a name? I'm going to use ascii value of each character in part to make life easier.

Let's say no more than 20 characters.

You don't need to do this problem in a very smart way to get it to work.

Jim-Bob might be a redneck if any of his relatives is a redneck, so...find all his relatives, and check if each one is a redneck!

How do you see if a person is a redneck? Figure it out - I won't give the WHOLE problem away =P

LoL give some hints on the new BiWeeklys please :)

We'll give hints on Bi-weekly Challenges after their values have been halved =P

=-= how is it i get ONE wrong in each testcase? T.T

Is the first person listed always Jim-Bob? Or can he be somewhere else in the list?

He's not always first, but he is always somewhere.