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.