W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W kraju działają agenci obcych wywiadów.
Zajmują się oni nie tylko wykradaniem tajemnic, ale także nawzajem się szpiegują.
Mówimy, że agent rozpracował agenta
, jeśli
posiada dokumenty wystarczające do aresztowania
.
Niektórzy agenci są przekupni — w zamian za odpowiednią sumę pieniędzy są gotowi oddać wszystkie posiadane dokumenty. Aresztując agenta przechwytujemy wszystkie zgromadzone przez niego dokumenty. Przekupienie odpowiednio wybranych agentów może więc uruchomić łańcuch aresztowań prowadzący do zlikwidowania wszystkich agentów działających w kraju.
Rodzimy kontrwywiad dostarczył nam informacje o tym, jacy obcy agenci działają w kraju,
którzy z nich są przekupni i za jaką cenę, a także,
którzy agenci rozpracowali których.
Liczba agentów ; są oni ponumerowani od
do
.
Ułóż program, który:
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba naturalna .
Jest to liczba wszystkich działających w kraju agentów,
.
W drugim wierszu jest zapisana jedna liczba naturalna
.
Jest to liczba wszystkich agentów przekupnych,
.
W kolejnych
wierszach są zapisane informacje o przekupnych agentach.
W każdym takim wierszu są zapisane dwie liczby całkowite dodatnie oddzielone odstępem —
pierwsza z nich jest numerem przekupnego agenta, a druga to suma,
za którą można go przekupić — jest to liczba nie większa niż
.
Kolejny wiersz zawiera jedną liczbę , gdzie
.
Jest to liczba takich par
, że agent
rozpracował agenta
.
W następnych
wierszach podane są wszystkie takie pary.
W każdym z tych wierszy są zapisane dwie różne liczby ze zbioru
oddzielone odstępem —
pierwsza, to numer agenta, który rozpracował, a druga, to numer agenta, który został rozpracowany.
W pierwszym wierszu standardowego wyjścia należy zapisać jedno słowo: TAK — jeśli istnieje możliwość aresztowania wszystkich agentów działających w kraju, albo NIE — jeśli taka możliwość nie istnieje. W drugim wierszu należy zapisać jedną liczbę całkowitą dodatnią: minimalny koszt zakupu informacji wystarczających, by doprowadzić do aresztowania wszystkich agentów w kraju, albo numer dowolnego agenta, którego nie da się zaaresztować.
Dla danych wejściowych:
3 2 1 10 2 100 2 1 3 2 3
poprawną odpowiedzią jest:
TAK 110
natomiast dla danych:
4 2 1 100 4 200 2 1 2 3 4
poprawnym wynikiem jest:
NIE 3
Autor zadania: Marcin Kubica.