LinkNet

Limit pamięci: 32 MB

W sieci LinkNet komputery są przyłączone do linii komunikacyjnej w sposób przedstawiony na rysunku. Dostępne punkty przyłączeń są ponumerowane kolejno . Do jednego punktu może być przyłączony tylko jeden komputer. Każdy z komputerów może być przyłączony do sieci tylko w jednym punkcie. Komunikacja w sieci jest synchroniczna.

W danym takcie komputery przyłączone do punktów mogą dokonać transmisji danych tylko wtedy, gdy żaden komputer przyłączony do łącza o numerze nie bierze udziału w transmisji danych z jakimkolwiek innym komputerem. W jednym takcie komputer może brać udział tylko w jednej tranmisji.

Zadanie

Napisz program który:

• wczytuje opisy transmisji, które trzeba zrealizować,
• oblicza jaka jest minimalna liczba taktów wystarczających do zrealizowania transmisji,
• wypisuje obliczoną liczbę.

Wejście

W pierwszym wierszu danych podana jest liczba transmisji : . W kolejnych wierszach podane są opisy transmisji - po jednym w wierszu. Opis każdej transmisji składa się z dwóch liczb : oznaczających numery punktów, pomiędzy którymi ma być transmisja danych. Liczby i są oddzielone spacją.

Wyjście

W pierwszym i jedynym wierszu wyniku powinna być podana jedna liczba: minimalna liczba taktów wystarczających do zrealizowania wszystkich transmisji opisanych w danych.

Przykład

Dla danych wejściowych:

4
10 20
3 10
5 35
20 50

poprawną odpowiedzią jest:

3