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
|
Tesztadatok
