Električar Mile je najbolji majstor koga ste ikada videli. Razume se u sve, brzo popravlja aparate, a pre svega nije skup. Jednog dana je otišao u obližnji grad Abenišbe da popravi nekoliko bandera. Kada je stigao zatekao je ogromnu mrežu. Bandere su bile razbacane po gradu, bez ikakvog rasporeda. Mile je rešio da preuzme stvar u svoje ruke: povadio je sve bandere i želi da ih postavi u jednu liniju, tako da je rastojanje između svake dve susedne bandere jednako 1 m. Naravno, sve veze moraju da ostanu na svojim mestima. Dužina žice koju treba da razvuče između dve bandere je jednaka rastojanju između njih u metrima (najkraće rastojanje). Mile želi da postavi bandere tako da ukupna dužina žice koju će potrošiti na povezivanje bude što je moguće manja.

Kako ovaj problem nije Miletov fah, obratio se vama - mladim programerima, da mu pomognete i pokažete mu raspored bandera, tako da minimizuje ukupnu dužinu žice. Kada sazna permutaciju bandera, Mile će začas da ih postavi i poveže.

Za ovaj zadatak potrebno je da predate izlazne datoteke za 10 ulaznih datotoka bandere.01.in, bandere.02.in, ..., bandere.10.in, koji se nalaze u arhivi na računaru. Izlazn se pamti u datoteke bandere.01.out, bandere.02.out, ..., bandere.10.out, pri čemu broj u nazivu izlazne datoteke odgovara broju u nazivu ulazne datoteke.

Ulaz:

(Ulazni podaci se nalaze u datoteci bandere.nn.in) U prvom redu ulazne tekstualne datoteke nalaze se dva prirodna broja n i m, koji predstavljaju broj bandera i broj međusobnih veza. U svakoj od sledećih m linije se nalaze dva prirodna broja a i b (1 ≤ a, b ≤ n), koji predstavljaju po jednu vezu - bandere sa rednim brojevima a i b su povezane žicom.

Izlaz:

(Izlazne podatke upisati u datoteku bandere.nn.out) U prvom redu izlazne tekstualne datoteke treba zapisati "#bandere, nn" (bez navodnika) gde umesto nn treba zapisati broj test primera. U drugom redu izlazne datoteke upisati minimalnu dužinu svih žica. U sledećem redu treba ispisati jednu permutaciju brojeva od 1 do n, koja predstavlja raspored bandera za datu dužinu.

Način bodovanja:

Broj bodova za svaki test primer se određuje na sledeći način: neka je dužina žice u vašem rešenju VAL, a OPT je minimalna dužina među svim takmičarima, uključujući i komisijska rešenja. Broj bodova koje dobijate se računa po formuli (zaokruživanje se vrši na prvi veći ceo broj): 10^{(3 - VAL/OPT)/2}

Drugim rečima, ako je vaše rešenje identično sa najboljim dobijate 10 poena. U slučaju da je rešenje duplo lošije - dobićete 1 poen. Za gornji test primer dobijamo 10^{(3 - 11/8)/2} = 6.49, pa je broj bodova 7. Ako je dužina koju navedete u izlaznom fajlu različita od stvarne dužine za datu permutaciju dobijate 0 poena za taj test primer.

Primer 1:

5 6
1 2
1 4
1 5
2 3
2 5
3 5

# bandere 00
11
2 3 1 5 4

Objašnjenje:

Na slici je prikazana mreža bandera koju treba "linearizovati". Rešenje iz primera ima ukupnu dužinu svih žica 11: dužina prve žice između bandere 1 i 2 je 2 m, dok je dužina treće žice za bandere 1 i 5 jednaka 1 m. Sličnim rasuđivanjem dobijamo da je ukupna dužina žica 2 + 2 + 1 + 1 + 3 + 2 = 11. Minimalna dužina je jednaka 8, na slici dole.