Fişierul intrare/ieşire: | plimbare.in, plimbare.out | Sursă | Summer Challenge 2 |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Plimbare
![]() Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema! |
In fiecare oras unde componentii lotului de informatica fac pregatiri inaintea olimpiadelor internationale, se organizeaza cate o plimbare pentru a vizita obiectivele turistice. Anul acesta orasul in care au ajuns olimpicii are proprietatea curioasa ca exista cate o strada intre oricare doua obiective, dar strada are un singur sens de mers.
Cerinta
Determinati o plimbare de lungime maxima care poate merge pe strazile orasului in sensul lor normal de mers, astfel ca la sfarsitul plimbarii sa ajungem la acelasi obiectiv de la care am pornit, iar fiecare strada sau obiectiv sa fie vizitat o cel mult o data (in afara de obiectivul de unde pornim care va fi vizitat de doua ori).
Date de intrare
In fisierul de intrare plimbare.in vom avea pe prima linie numarul N de obiective. Pe urmatoarele N*(N-1)/2 linii vor fi cate doi intregi x, y separati prin exact un spatiu, cu semnificatia ca intre obiectivul x si obiectivul y exista o strada cu sensul de la x la y.
Date de Iesire
Fisierul de iesire plimbare.out va contine pe prima linie numarul P maxim de obiective pe care le putem vizita intr-o asemenea plimbare. Urmatoarea linie va contine P intregi separati prin spatiu, care ne vor da obiectivele vizitate si ordinea vizitarii lor.
Restrictie
- 1 ≤ N ≤ 100
Exemplu
plimbare.in | plimbare.out |
---|---|
4 1 2 1 4 2 3 3 1 3 4 4 2 | 4 1 4 2 3 |
Explicatie
Cea mai lunga plimbare este una ce viziteaza toate cele 4 obiective. Obiectivele vor fi vizitate in ordinea 1->4->2->3->1.