PROBLEMA 44:		VERIGI
DOMENIU:		Backtracking, grafuri
TIMP DE IMPLEMENTARE:	O ora
DEADLINE:		Marti, 11 aprilie 2000
PUNCTAJ:		50 dexteri

Aceasta problema a fost propusa la finala de anul acesta a concursului
ACM. M-am gandit ca este o experienta interesanta sa vedeti cam ce gen
de probleme se propun la ACM.

Ana a cumparat de la magazin n verigi de aur. Unele perechi de verigi
sunt legate intre ele (sunt petrecute una prin alta). Ana isi doreste
sa recombine aceste verigi pentru a obtine un singur lant de n
verigi. Ea se duce la bijutier, care ii spune ca pretul operatiei va
depinde de numarul de verigi care trebuie deschise pentru a forma un
singur lant. De aceea, Ana doreste sa stie care este numarul minim de
verigi care trebuie dechise. Primul exemplu prezentat mai jos va este
probabil cunoscut ca o problema de logica.

Datele de intrare se dau in fisierul text VERIGI.IN care contine
urmatoarele date:

n m
a1 b1
a2 b2
.....
am bm

unde n este numarul de verigi (3<=n<=20), iar m este numarul de
perechi de verigi trecute una prin cealalta. Urmatoarele m perechi
(ai,bi) indica perechile de verigi care sunt legate.

Datele de iesire se vor scrie in fisierul VERIGI.OUT sub forma:

k
v1 v2 ... vk

unde k este numarul minim de verigi care trebuie deschise, iar v1, v2,
..., vk este o posibila configuratie de verigi care vor fi deschise.

Exemple:

VERIGI.IN				VERIGI.OUT
15 10					3
1 2					1 2 3
2 3
4 5
5 6
7 8
8 9
10 11
11 12
13 14
14 15

Semnificatie: Se desface complet primul din cele cinci fragmente, iar
cele trei verigi rezultate se folosesc pentru a conecta celelalte
patru fragmente.

VERIGI.IN				VERIGI.OUT
5 6					1
1 2					3
2 3
3 1
3 4
4 5
5 3

Semnificatie: Se desface veriga 3, care apoi se trece prin verigile 1
si 4 si se inchide.

TIMP DE RULARE: O secunda/test.