TLE '15 P6 - Rock, Paper, Scissors

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You certainly know the game Rock, Paper, Scissors. You might know of some variants of Rock, Paper, Scissors, such as Rock, Paper, Scissors, Lizard, Spock, or Rock, Paper, Scissors, Fox.

However, this is the year 20XX. Rock, Paper, Scissors has evolved into Rock, Paper, Scissors 20XX (RPS20XX), where there are thousands of different options. Naturally, people became competitive and wanted to beat others in this exciting game.

Of course, Fax McClad, Croneria's most talented bounty hunter, is very good at RPS20XX. In fact, he is so good that he is banned from participating at every single RPS20XX tournament in existence. Instead, he attends these tournaments since people want his expert opinions.

At one specific RPS20XX tournament for top competitors, there are participants, numbered from to . Fax wants to compare participants, but he only knows matchups. Each matchup consists of two participants signifying that the first participant directly beats the second participant. It is guaranteed that two participants cannot directly beat each other. A participant indirectly beats another participant if the former can beat somebody who directly or indirectly beats the latter.

From these matchups, we can determine the relative skill level of the participants. In particular, a participant is better than another participant if and only if can beat directly or indirectly, but cannot beat directly or indirectly.

In addition, if two participants can be compared, a number representing the skill difference is assigned, called the Matchup Excitement Value (MEV). The MEV between participants and , if is better, is the number of participants in the largest possible subset of all participants that satisfy the following properties:

• is better than each participant in the subset and each participant is better than .
• Between any two participants in the subset (if there are more than 1), at least one must be able to directly or indirectly beat the other.

Fax is given queries. Each query consists of the numbers of two participants. Fax is to determine the better participant and the MEV, or if it is not determinable. Please help Fax accomplish this task.

Input Specification

The first line consists of three integers: , , and .

The next lines will contain two space-separated integers and , signifying that participant can beat participant .

The next lines will each contain a query in the form of two space-separated integers and , the numbers of two participants.

Output Specification

For each query, output two integers signifying the number of the better participant and the MEV between the two participants, or Indeterminate if the two participants cannot be compared. The answer(s) to each query should be on separate lines.

Sample Input

6 7 4
1 2
2 3
3 1
1 4
2 5
4 6
5 6
3 5
1 3
4 5
2 6

Sample Output

3 0
Indeterminate
Indeterminate
2 1

Explanation for Sample Output

For the first query, 3 is better than 5 and no participant is better than 5 and worse than 3.

For the second query, 3 directly beats 1 but 1 indirectly beats 3, so they cannot be compared.

For the third query, neither 4 nor 5 directly or indirectly beat each other, so they cannot be compared.

For the fourth query, 2 is better than 6. There are two participants better than 6 and worse than 2 (participants 4 and 5), but neither of the two participants can beat each other. Therefore, the MEV between participants 2 and 6 is only 1.

• commented on Aug. 2, 2017, 2:40 p.m.

Can someone explain the sample output: how are participants 4 and 5 worse than 2 and better than 6 as it states in the explanation for sample output

• commented on Aug. 2, 2017, 8:49 p.m. edited

2 directly beats 5; 2 beats 3, 3 beats 1, 1 beats 4.

4 directly beats 6; 5 directly beats 6.

• commented on March 21, 2016, 7:16 p.m. edited

I just submitted problem in the morning. What happened?