AlgoLiga 2018

"Domino to gra dla dwóch osób.

W grze wykorzystuje się kamienie(domina), które mają kształt prostokątów, na których obydwu końcach znajduje się pewna liczba oczek od 0 do 6. W zestawie do gry występują klocki z każdą kombinacją oczek i każda kombinacja występuje dokładnie jeden raz" - taka jest definicja gry domino.

Bitek i jego wuj Bajtosław w wolnych chwilach grywają w tą wspaniałą grę, jednak ile można grać ciągle w to samo. Warcaby klasyczne też już dawno się znudziły. Nagle młody gracz wpadł na genialny pomysł i powiedział: "Zmieńmy zasady gry DOMINO!". Wuj chętnie wysłuchał pomysłu Bitka i dodał kilka swoich sugestii, co w rezultacie zaowocowało taką grą:

Układamy losowo wszystkie dostępne kamienie w jeden długi ciąg, w którym klocki nie muszą być poprawnie ułożone (nie musi się zgadzać liczba oczek w dwóch sąsiadujących kamieniach). Gra polega na tym, że gracze wykonują ruchy na przemian obracając wybrany kamień, który jest nieprawidłowo dopasowany w ten sposób, aby liczba oczek dla jednej płytki z lewej i prawej strony się zgadzała. Klocków domina nie można przestawiać miejscami. Dodatkowo, liczba kamieni domina jest znacznie większa, niż w standardowej grze oraz mogą one się powtarzać. Nie zmienia się natomiast liczba dopuszczalnych oczek. Przegrywa osoba, która nie będzie mogła wykonać ruchu.

Twoje zadanie jest następujące: dla ustalonego ciągu klocków określ maksymalny spójny podciąg, który będzie można utworzyć obracając kamienie domina tak, że będzie on tworzył poprawny podciąg gry DOMINO.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość kości domina (1 ≤ n ≤ 2⋅10⁶).

W następnym wierszu n kości domina. Każda kość jest w formacie: [oczka1]|[oczka2], gdzie oczka1 i oczka2 oznaczają ilość oczek po jednej i drugiej stronie domina np.:

zapis 4|5 oznacza kość

Wyjście

Jedna liczba określająca długość najdłuższego spójnego podciągu, który spełnia zasady gry DOMINO.

Przykład 1

Wejście:
8
2|2 3|5 1|1 1|6 5|6 6|4 2|4 4|0

Wyjście:
3

Przykład 2

Wejście:
4
6|6 6|2 6|2 6|1

Wyjście:
4

Wyjaśnienie:

W pierwszym przykładzie przekręcamy kamień piąty i uzyskujemy podciąg:

1|1 1|6 6|5

lub kamień siódmy i mamy podciąg:

5|6 6|4 4|2

W drugim przykładzie obracając trzeci kamień uzyskujemy ciąg o długości 4.