Pierwotek abstrakcyjny

Limit pamięci: 32 MB

Kod genetyczny pierwotka abstrakcyjnego (Primitivus recurencis) jest ciągiem liczb naturalnych, . Cechą pierwotka nazywamy każdą parę liczb , które występują kolejno w kodzie genetycznym, tzn. istnieje takie, że , . U pierwotków nie występują cechy postaci .

Zadanie

Napisz program, który:

• wczyta listę cech ze standardowego wejścia,
• obliczy najmniejszą długość najkrótszego kodu genetycznego pierwotka zawierającego podane cechy,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita . Jest to liczba różnych cech pierwotka. W każdym z kolejnych wierszy znajduje się para liczb naturalnych i oddzielonych pojedynczym odstępem, , . Para jest jedną z cech pierwotka. Cechy w danych wejściowych nie powtarzają się.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia dokładnie jedną liczbę całkowitą, równą długości najkrótszego kodu genetycznego pierwotka zawierającego cechy podane na wejściu.

Przykład

Dla danych wejściowych:

12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6

poprawną odpowiedzią jest:

15

Wszystkie cechy z przykładu są zawarte np. w następującym kodzie genetycznym: (8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6).

Autor zadania: Wojciech Rytter.