O - Okružný let

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Sponzor PALMA Airlines ponúkol najlepšiemu programátorovi naozaj výnimočnú cenu. Letecký výlet do vybraných letísk, z ktorých a do ktorých premávajú lietadlá tejto spoločnosti. Letiská si vyberá výherca, no musí dodržať tieto pravidlá:

Výlet začína odletom z letiska Košice a končí príletom na letisko Košice.
Počas výletu výherca používa výhradne letecké linky spoločnosti PALMA Airlines (všetky linky leteckej spoločnosti sú obojsmerné, medzi dvoma letiskami je len jedna linka).
Na žiadne letisko nesmie výherca priletieť viac ako raz.

Nuž a aby si najlepší programátor cenu vôbec mohol zaslúžiť, mal by vedieť nájsť taký plán výletu, pri ktorom navštívi najviac letísk.

Úloha

Daný je zoznam obojsmerných leteckých liniek spoločnosti PALMA Airlines. Vytvorte program, ktorý zistí, koľko najviac letísk je možné počas výletu v súlade s pravidlami navštíviť. Letisko Košice nerátame.

Vstup

Prvý riadok obsahuje trojicu medzerou oddelených čísel N, K a M, kde N (1 ≤ N ≤ 11) je počet mimokošických letísk, K (0 ≤ K ≤ N) je počet letísk, do ktorých je priama linka z/do Košíc a M je počet obojsmerných leteckých liniek PALMA Airlines medzi mimokošickými letiskami. Letiská sú očíslované od 0 po N-1, pričom priame letecké linky z/do Košíc sú z/do letísk označenými číslami od 0 po K-1. Ďalej bude nasledovať M riadkov popisujúcich letecké linky. Každý riadok obsahuje medzerami oddelené dve čísla reprezentujúce letiská (ich číselné označenia), medzi ktorými táto letecká linka premáva.

Výstup

Vypíšte maximálny počet mimokošických letísk, ktoré je možne navštíviť počas výletu.

Príklad

Vstup:

Výstup:

20 Finále