Szerkezetek
Szamanta kapott szülinapjára néhány gömbcsuklós szerkezetet. Ezekből az ábrákon látható módon lehet építeni, az egyenlő hosszú rudak a gömbcsuklóknál tetszőlegesen forgathatók. A játék befejeztével szeretné eltenni a szerkezeteket, méghozzá egy szögre felakasztva úgy, hogy egyetlen egyenes "vonallá" legyenek összecsukva. Ha ez megoldható, még azt is szeretné, hogy a "vonal" a lehető legrövidebb legyen.
Az első szerkezet összecsukása látható a második rajzon, a harmadik ábra szerkezete pedig nem csukható össze.
Feladat
Szamanta nem túl jó programozó, segítsünk neki, írjunk programot a legjobb összecsukás hosszának kiszámítására, illetve annak eldöntésére, hogy lehetséges-e egyáltalán "vonallá" összecsukni a szerkezetet.
Bemenet
A bemenet több tesztesetet tartalmaz. Ezek üres sorokkal vannak elválasztva. A bemenet végét egy "0 0"-át sor jelzi.
Egy teszteset első sora a gömbök $G$ és a rudak $R$ számát tartalmazza. ($1\le G \le 100, 1 \le R \le 1000$) A következő $R$ sor a rudak végpontjaiban lévő gömbök sorszámait adja meg.
Kimenet
Minden tesztesethez írjuk ki a legrövidebb összecsukás hosszát (az ábrán 2), vagy az
"impossible" szöveget, ha nem csukható össze a szerkezet.
Példa
| szerkezet.be | szerkezet.ki |
|
6 6 1 2 5 6 3 2 3 5 4 2 4 5 4 5 1 2 2 3 3 4 1 3 2 4 0 0 |
2 impossible |