Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
?

FR_03_13 - DOMINO II

Dziś są dni otwarte Bajtlandzkiej uczelni. Każdy może zapoznać się z wykładowcami, porozmawiać z nimi na różne tematy i przede wszystkim zmierzyć się z nimi intelektualnie. Profesor Algobit przygotował dla swoich potencjalnych studentów grę domino składającą się z 28 kamieni. Na obydwu końcach każdego klocka znajduje się pewna liczba oczek należąca do zbioru {0, 1, 2, 3, 4, 5, 6} oraz każda kombinacja występuje dokładnie raz. Uczniowie szkół ponadgimnazjalnych chętnie podchodzili do stanowiska profesora będąc przekonani, że za chwilę rozegrają fascynującą grę w domino. Niestety bardzo się mylili. Wykładowca rozdał dwa zestawy po tyle samo kamieni - jeden dla siebie, drugi dla swojego przeciwnika, odkrył wyszystkie kamienie i zadał pytanie: "Jeśli ja zaczynam grę i każdy z nas będzie dokładał kamienie zgodnie z zasadami gry domino w taki sposób, że jeśli po zakończonej grze weźmiemy ze stołu dwa dowolne sąsiadujące ze sobą kamienie, to jeden będzie mój a drugi twój, to ile maksymalnie może znaleźć się kamieni na stole?". Zadanie okazało się twardym orzechem do zgryzienia. Jeśli chcesz podejść do profesora Algobita, to wcześniej napisz program, który rozwiąże tą zagadkę, a wiedz, że wtedy profesor zarekomenduje twoje umiejętności.

domino

Wejś›cie

W pierwszym wierszu liczba n określająca liczbę zestawów danych (n ≤ 103).

Każdy zestaw składa się z jednej liczby n określającej po ile kamieni będzie rozdane dla każdego z przeciwników (n należy do zbioru {1, 2, 3, .., 14}. W następnych dwóch wierszach po dwie porcje po n kamieni domina. Pierwszy zestaw to kamienie prof. Algobita, zaś drugie Twoje.

Każdy kamień jest zapisany w postaci: [liczba oczek]|[liczba oczek] np. 3|0. Liczba oczek to liczba należąca do zbioru {0, 1, 2, 3, 4, 5, 6} oraz kamienie są unikatowe.

Jest tylko kilka przypadków testowych, w których znajduje się maksymalna liczba kamieni.

Wyjś›cie

Dla każdego zestawu jedna liczba określająca maksymalną długość kamieni domina przy optymalnej grze, jeśli wiadomo, że pierszy ruch należy do profesora Algobita.

Przykł‚ad

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

Wyjście:
2
4
4
2

Wyjaśnienie dla drugiego zestawu testowego:

Dane kamienie można połączyć w następujący sposób (czerwone kamienie należą do ciebie):
2|6 6|4 4|4 4|5

Dodane przez:Marcin Kasprowicz
Data dodania:2015-03-08
Limit czasu wykonania programu:1s-6s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.