Planet of the Rock, Paper and Scissors

It’s the twenty-fifth century now and space exploration finaly came to full maturity. Recently, on a small green planet in one of the neighboring spiral arms of our galaxy, a hitherto unknown species was discovered. Obeying interplanetary laws, earth scientists are allowed to study this new species, but they can not interfere in any way with them. So they use large telescopes and study it’s behaviour from one of the planet’s moons. The preliminary research reveal the following facts: • Every individual belongs to one of three races. The names for these races given by the scientists are “Rock”, “Paper” and “Scissors”. (If you think that these names are strange, take a 101 course is quantum chromodynamics). • Indiviuals from different races look exactly alike, but when two individuals from different races meet each other the difference becomes clear. During the encounter one individual completely dominates the other according to the following rules: – Rock dominates Scissors; – Scissors dominates Paper; – Paper dominates Rock. • Encounters between individuals of the same race never happen. • Individuals live in closed communities of varying sizes. There are no encounters between individ- uals of different communities. To study the new species, the communities are permanently observed by the telescopes. The images are interpreted by special tracking software that registers the moves of every individual. Everytime an encounter between two individuals occurs, this fact is recorded, together with information about which individual dominates during the encounter. Your task is to write a program that reads the records and decides wether it is possible to uniquely determine the race of every individual within a community under study, once an arbitrary race is assigned to one of the individuals. Input The first line gives the number of communities studied (max. 1000). For each community there is a line containing the number of individuals within the community (max. 5000), and the number of encounters recorded, followed by the records of each encounter. A record has the format (M > N), which means that the individual numbered M dominates the individual numbered N. Individuals are numbered uniquely by the tracking software from 1 to S, where S is the community size. The records are grouped in lines, with a maximum of ten per line. No whitespace, apart from the line breaks will occur. You may assume that every member of a community is engaged in an encounter at least once. Output Per community in the input file one line stating the community number (numbering sequentially from 1) followed by one of three statements (without the quotes):

2/2 • ‘Observation Complete’. Although the races can’t be determined by direct observation, once we arbitrarily assign a race to one individual, the race of every other individual can be uniquely determined. • ‘Not Enough Data’. The race of one or more individuals can’t be determined, even though we assign the race of one individual arbitrarily. • ‘Conflicting Records’. Something went wrong during the observations, the assignment of the races leads to a conflict. See the sample output for the exact format. The results ‘Not Enough Data’ and ‘Conflicting Records’ can occur simultaniously. In this situ- ation your program should report ‘Conflicting Records’ because the observations for this community will have to be redone from scratch. Explanation For Community 1 we arbitrarily assign Rock to individual 6. Because individuals 1, 2 and 3 are dominated by it, they should be Scissors. Now individuals 4 and 5 are both dominated by a Scissors, which means they are Paper. Finaly individual 7 is dominated by individual 5 (a Paper) so it’s a Rock. We now have 2 Rocks (6 and 7), 3 Scissors (1, 2 and 3) and 2 Papers (4 and 5), so all individuals are assigned a race and no conflicts occured. The result is therefore ‘Observation Complete’. In Community 2 we can arbitrarily assign Paper to individual 8, which makes 2, 4 and 6 Rock and 1 and 3 Scissors. Although there are redundant observations in the input, they don’t lead to conflicts. However we can not determine the races of 5, 7 and 9, although we know their mutual dominations, so the result is ‘Not Enough Data’. The first three observations of Community 3 would lead to the conclusion that individuals 1, 2 and 4 are Paper after arbitrarily assigning Scissors to individual 3. The fact however that 1 dominates 2 leads to ‘Conflicting Records’. The records for Community 4 lead to both ‘Not Enough Data’ and ‘Conflicting Records’. Ac- cording to the rules, ‘Conflicting Records’ is printed. Sample Input 4 76 (6>1)(6>2)(6>3)(1>4)(2>5)(5>7) 9 11 (8>4)(8>2)(8>6)(4>3)(2>3)(2>1)(6>1)(3>8)(1>8) (5>7)(7>9) 68 (3>1)(3>2)(3>4)(1>2)(4>2)(2>5)(2>6)(6>4) 87 (1>2)(2>3)(3>4)(4>5) (6>7)(7>8)(6>8) Sample Output Community 1: Observation Complete Community 2: Not Enough Data Community 3: Conflicting Records Community 4: Conflicting Records