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.
Input
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).
Output
For each case, simply output "Redneck" or "Not a redneck", depending on whether or not Jim-Bob is related to any rednecks.
Sample Input
1 6 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
Explanation
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:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
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