Porachunki
Limit pamięci: 32 MB
Firma Bajtosoft zatrudnia pracowników. Z powodu tajności projektów przez nią
wykonywanych, nie wszyscy spośród nich się znają.
Znają się ze sobą tylko ci, którzy zajmują się kolejnymi fazami
pracy nad projektami.
Każdy projekt jest opracowywany w sposób sekwencyjny: najpierw pracownik
nr (szef zespołu) tworzy pierwszy szkic projektu, następnie przekazuje
go pracownikowi nr ; ten po wykonaniu swojego zadania efekt pracy
przekazuje pracownikowi nr , i tak dalej, aż w końcu projekt trafia do
pracownika nr , który kończy pracę nad nim i przekazuje
gotowy produkt szefowi (pracownikowi nr ).
Każdy pracownik ma w umowie zapisaną wysokość pensji, która mu
przysługuje. Jednak firma nie zawsze dobrze wywiązuje się z umowy i choć
zawsze wypłaca w sumie tyle pieniędzy swoim pracownikom, ile im się łącznie należy,
to jednak nie zawsze wypłaca pieniądze właściwym osobom.
Często zdarza się tak, że pewna osoba dostaje mniej pieniędzy, niż ma
to zagwarantowane w umowie, zaś inna dostaje więcej, niż powinna.
Na szczęście pracownicy są uczciwi, dlatego umówili się, że po każdej
wypłacie będą między sobą regulować wysokość otrzymanej pensji, tak
aby ostatecznie każdy otrzymał dokładnie tyle, ile ma zagwarantowane
w umowie.
Mają tylko jeden problem: przekazywać między sobą pieniądze mogą tylko
ci pracownicy, którzy się znają, tzn. dla każdego pracownik
nr może przekazać lub otrzymać pieniądze jedynie od pracowników nr
oraz , pracownik nr może dokonywać transakcji
z pracownikami nr oraz nr , zaś pracownik nr może dokonywać
transakcji z pracownikami nr oraz nr .
Ponieważ każde takie wyrównywanie płac wymaga wielu transakcji, pracownicy
Bajtosoftu poprosili Ciebie, niezależnego programistę, o napisanie programu,
który po każdej wypłacie wyznaczy minimalną liczbę transakcji potrzebnych
do wyrównania rachunków.
Zakładamy tutaj, że pracownicy wykorzystują w transakcjach tylko te sumy
pieniędzy, które otrzymali w ramach danej wypłaty od firmy, oraz te, które
otrzymali od innych pracowników w poprzednich transakcjach.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita
() oznaczająca liczbę pracowników Bajtosoftu.
W każdym z następnych wierszy znajdują się dwie liczby całkowite
oraz (), oddzielone pojedynczym odstępem i oznaczające
pensję -tego pracownika zagwarantowaną w umowie oraz ilość pieniędzy,
którą otrzymał w rzeczywistości (wyrażone w bajtalarach).
Możesz założyć, że .
Możesz założyć, że w testach wartych łącznie punktów zachodzi ,
a w podzbiorze tychże testów wartym punktów -
dodatkowe ograniczenie: .
Wyjście
Twój program powinien wypisać w pierwszym i jedynym wierszu standardowego wyjścia
jedną liczbę całkowitą oznaczającą minimalną liczbę transakcji pomiędzy
znającymi się pracownikami, która doprowadzi do stanu, w którym
każdy pracownik otrzyma ostatecznie (po uwzględnieniu wszystkich
transakcji) tyle pieniędzy, ile ma zagwarantowane w umowie.
W przypadku gdy żaden zestaw transakcji nie doprowadzi do takiego
stanu, należy wypisać jedno słowo "NIE".
Przykład
Dla danych wejściowych:
4
10 13
5 4
5 6
8 5
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu: Wyrównanie wszystkich pensji następuje
w dwóch krokach: pracownik nr 3 przekazuje pracownikowi nr 2 jednego
bajtalara, a pracownik nr 1 przekazuje pracownikowi nr 4 trzy bajtalary.
Autor zadania: Marian M. Kędzierski.