hamilton

Dubota este acum poliţist în toată regula şi a primit misiunea de a patrula $N$ obiective strategice. Cele $N$ obiective sunt conectate prin $M$ drumuri bidirecţionale. Dubota vrea să găsească un traseu cât mai lung de obiective pe care să patruleze. Un traseu este o succesiune de noduri $o_1, o_2, \dots o_K$ astfel încât $o_i \neq o_j$, $\forall i \neq j$ şi există drum de la $o_i$ la $o_{i+1}$ pentru $1 \leq i < K$ şi drum între $o_1$ si $o_K$.

Cerință

Sa se găsească un traseu cât mai lung de obiective pe care Dubota să-l patruleze.

Date de intrare

Pe prima linie a fisierului x-hamilton.in se găsesc două numere, $N$ şi $M$. Pe urmatoarele $M$ linii sunt cate $2$ numere, $u$, $v$, reprezentând un drum de la obiectivul $u$ la obiectivul $v$.

Date de ieșire

Pe prima linie a fişierului x-hamilton.out se va găsi lungimea celui mai lung traseu găsit, urmat pe a doua linie de descrierea ciclului, prin indicarea indicilor nodurilor de pe traseu.
Vi se pun la dipozitie cele $10$ fişiere de intrare care sunt folosite pentru evaluare, avand numele 0-hamilton.in, 1-hamilton.in $\dots$ 9-hamilton.in. Pentru fiecare fişier de intrare x-hamilton.in se cere să generaţi un fişier de ieşire x-hamilton.out în care să scrieţi traseul cerut. Fişierele vor fi trimise unul câte unul.

Restricții și precizări

• Punctajul pe un test se calculeaza astfel, unde $K$ e lungimea drumului afisat:
  • Pentru $N \leq 5000$: $\max(0, 10 - N + K)$
  • Pentru $N > 5000$: $\lfloor 10 \cdot \left( \frac{K}{N} \right)^6 \rfloor$.

Exemplu

hamilton.in

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

hamilton.out

8
1 2 3 5 8 7 4 6