TLE '15 P6 - Rock, Paper, Scissors

View as PDF

Submit solution

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

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 N participants, numbered from 1 to N. Fax wants to compare participants, but he only knows M 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 A is better than another participant B if and only if A can beat B directly or indirectly, but B cannot beat A 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 A and B, if A is better, is the number of participants in the largest possible subset of all participants that satisfy the following properties:

  • A is better than each participant in the subset and each participant is better than B.
  • 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 Q 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.


Subtask 1 [20%]

2 \le N \le 20

1 \le M \le \dfrac{N(N-1)}{2}

1 \le Q \le 100

Subtask 2 [80%]

2 \le N \le 5\,000

1 \le M \le \min\left(10^4,\dfrac{N(N-1)}{2}\right)

1 \le Q \le 100\,000

Input Specification

The first line consists of three integers: N, M, and Q.

The next M lines will contain two space-separated integers A and B (1 \le A,B \le N, A \ne B), signifying that participant A can beat participant B.

The next Q lines will each contain a query in the form of two space-separated integers X and Y (1 \le X,Y \le N, X \ne Y), 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
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.


  • 1
    septence123  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

    • -1
      wleung_bvg  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.

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

    I just submitted problem in the morning. What happened?