8539번 - LinkNet 다국어

W sieci LinkNet komputery są przyłączone do linii komunikacyjnej w sposób przedstawiony na rysunku. Dostępne punkty przyłączeń są ponumerowane kolejno 0, 1, ..., R. 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 0 ≤ a < b ≤ R mogą dokonać transmisji danych tylko wtedy, gdy żaden komputer przyłączony do łącza o numerze c, a < c < b nie bierze udziału w transmisji danych z jakimkolwiek innym komputerem. W jednym takcie komputer może brać udział tylko w jednej tranmisji.

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ę.

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

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