Un problema de caribbean online judge

1813 - Strange Regulations

Descripción

Thank to cryptography, we are able to encrypt messages such that none (except the intended recipient) is able to read them. However, encrypted messages are of no use if they do not actually reach the recipient. These days, computer network is the most typical mean to send such messages. In this problem, we will study the issues the networking providers have to solve. And remember: since the message is encrypted, we do not need to care about the network privacy anymore.

The network cables joining computers (servers) belong to different companies. A new anti-monopoly legislation prevents any company from owning more than two cables from each server. Furthermore, to avoid wasting resources, there is also a law specifying that the cable system owned by any single company cannot be redundant, i.e., removal of any of the cables will disconnect some two previously connected servers. Since the companies buy and sell the cables all the time, it is quite difficult to enforce these regulations. Your task is to write a program that does so.

Especificación de entrada

The input contains several instances. The first line of each instance contains four integers N, M, C and T separated by spaces - the number of servers (1 <= N <= 8000), the number of cables (0 <= M <= 10^5), the number of companies (1 <= C <= 10^2), and the number of cable-selling transactions (0 <= T <= 10^5), respectively.

The following M lines describe the cables. Each of them contains three integers Sj1 , Sj2 and Kj , separated by spaces, giving the numbers of the servers Sj1 and Sj2 (1 <= Sj1 < Sj2 <= N) joined by that cable and the number of the company Kj (1 <= Kj <= C) initially owning the cable. For each pair of servers, there is at most one cable joining them. The initial state satisfies the regulations, i.e., each company owns at most two cables incident with each server, and the system of cables owned by a single company has no cycles.

Finally, each of the next T lines contains integers Si1 , Si2 and Ki describing one transaction in which the company Ki (1 <= Ki <= C) tries to buy a cable between servers Si1 and Si2 (1 <= Si1 < Si2 <= N).

The last instance is followed by a line containing four zeros.

Especificación de salida

For each input instance, output T lines describing the outcome of the transactions. The possible outcomes are:

• "No such cable." if the pair of servers is not joined by a cable,
• "Already owned." if the cable is already owned by the company Ki,
• "Forbidden: monopoly." if the company Ki already owns two cables at Si1 or Si2,
• "Forbidden: redundant." if Ki owns at most one cable at each of Si1 and Si2, but granting the ownership would create a cycle of cables owned by Ki,
• "Sold." if none of the above restrictions apply. In this case, the ownership of the cable between Si1 and Si2 changes to Ki for the purpose of further transactions.
• Print one empty line after each instance.

Ejemplo de entrada

4 5 3 5
1 2 1
2 3 1
3 4 2
1 4 2
1 3 3
1 2 3
1 2 3
1 4 3
2 3 3
2 4 3
2 1 1 1
1 2 1
1 2 1
0 0 0 0

Ejemplo de salida

Sold.
Already owned.
Forbidden: monopoly.
Forbidden: redundant.
No such cable.

Already owned.

Sugerencia(s)

Origen	2010/2011 ACM-ICPC Central Europe Regional Contest
Adicionado por	ymondelo20
Fecha de adición	2012-04-22
Tiempo límite (ms)	10000
Memoria límite (kb)	130000
Salida límite (mb)	64
Tamaño límite (bytes)	30000
Languages activados	C  C#  C++  Java  Pascal  Perl  PHP  Python  Ruby  Text