Wizard Duel

reborn National Girls' Programmi...
Limits 1s, 512 MB

Wizard Duel is approaching soon in Hogwarts and the students of the Dueling Club are absolutely thrilled! One more time, they can show off their skills in front of the whole school in a fun, yet sincere competition against each other. It is a competition where in each round, a wizard/witch faces off against another wizard/witch in a friendly battle of witchcraft and wizardry.

Hermione, being the clever girl she is, wants to pick her battles carefully. Each wizard and witch has a fixed power in her eyes. The value of the power of any wizard, she couldn’t determine. But what she does know, is the ratio of power between a few pairs of wizards and/or witches. She is wondering, given the information she has, if it is possible to know that in a battle of one wizard vs another, who will win?

Formally, there are NN wizards and witches (including Hermione). Each of them has PiP_i fixed powers, but that value is unknown to Hermione. She does know, however, that the powers are positive and the ratio of PiP_i and PjP_j (i.e. pipj\frac{p_i}{p_j}) for MM pairs of wizards and witches (i,j)(i, j).

Hermione has QQ queries, each of them asks that in a battle of wizard ii and wizard jj, is it possible to know who will win given the information she has? If yes, then who wins? Is it a draw instead?

Note that, a wizard ii will win against another wizard jj if the former has more power i.e. Pi>PjP_i > P_j. And they will draw if they have equal power i.e. Pi=PjP_i = P_j.


The first line of input contains an integer T(1T100)T (1 \le T \le 100) denoting the number of test cases.

For each test case, the first line contains three integers N,M,QN, M, Q.

  • 2N352 \le N \le 35.

  • 1M,QN(N1)21 \le M, Q \le \frac{N(N-1)}{2}.

MM lines follow, each containing four integers i,j,x,yi, j, x, y meaning that the ratio of power between wizards ii and jj is xy\frac{x}{y} (i.e. PiPj=xy\frac{P_i}{P_j} = \frac{x}{y}). You can safely assume that iji \neq j. Furthermore, the values xx and yy will be co-prime to each other i.e. gcd(x,y)=1gcd(x, y)=1. You can also assume that each of the information regarding the ratio of powers will be consistent throughout a test case. No two unordered (i,j)(i, j) pair will be the same in a test case.

  • 1i,jN1 \le i, j \le N and iji \neq j.

  • 1x,y31 \le x, y \le 3 and gcd(x,y)=1gcd(x,y) = 1.

Another QQ lines follow, each containing two integers a,ba, b describing the queries. For each of these queries, Hermione wants to know who will win in the battle between wizards aa and bb.

  • 1a,bN1 \le a, b \le N and aba \neq b.


For each query, output a string on a line. For a query (a,b)(a, b), you should output —

  • win” if wizard aa will win against bb.

  • lose” if wizard aa will lose against bb.

  • draw” if the wizards have equal power and will draw.

  • unknown” if it cannot be decided who will win or draw, based on the information Hermione has.

Please note that, you should print these strings without the quotes. Refer to the sample I/O for clarity.


4 2 3
1 2 2 3
3 2 2 1
1 2
3 1
2 4
2 1 1
1 2 1 1
2 1

Explanation for the Sample I/O

The first three lines in output correspond to the queries of test case 11. The last line corresponds to the query of test case 22.

In test case 11,

  • P1P2=23\frac{P_1}{P_2} = \frac{2}{3}, thus wizard 11will lose against wizard 22.

  • P3P1=3\frac{P_3}{P_1} = 3, thus wizard 33 will win against wizard 11.

  • there is no information about wizard 44, thus it is unknown who will win between wizards 22 and 44.

In test case 22,

  • Wizard 11 and 22 have equal power, thus it will be a draw.


Login to submit.


73% Solution Ratio
user.0039Earliest, 4w ago
AIUB_SingularityFastest, 0.0s
dip_BRURLightest, 4.9 MB
naeem4265Shortest, 1610B
Toph uses cookies. By continuing you agree to our Cookie Policy.