NézetNyomtat

Szerkezetek (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok

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.beszerkezet.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