Fişierul intrare/ieşire:strazi.in, strazi.outSursăpreONI 2008 Runda 3
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Strazi

Bursuc nu mai scrie poezii, nu mai canta la chitara, nici macar nu mai rezolva probleme de info si de aceea va roaga pe voi sa-l ajutati cu urmatoarea problema. Un prieten de-al lui din satul Fribsd l-a rugat sa-l ajute sa fluidizeze circulatia din sat. In sat exista N case numerotate de la 1 la N si M poteci pe care se poate circula doar intr-un singur sens. O poteca ce leaga casa A si casa B permite oamenilor sa ajunga de la casa A la casa B (sensul este unic, deci mergand pe aceasta poteca nu se poate ajunge de la casa B la casa A). Bursuc mai stie ca nu este posibil ca plecand de la o casa oarecare A si mergand doar pe potecile existente momentan sa se ajunga tot la casa A. Cateodata vin oaspeti in sat si acestia ar dori sa viziteze toate casele exact o singura data plimbandu-se numai pe poteci. Altfel spus ar dori sa existe o insiruire de case X1, X2, X3 .. XN astfel incat sa existe o poteca intre casele Xi si Xi+1 pentru fiecare i≤N-1. Momentan acest lucru nu este posibil, de aceea trebuie construite un numar minim de poteci astfel incat sa existe un asemenea drum.

Date de intrare

Fisierul de intrare strazi.in contine pe prima linie doua numere N si M avand semnificatia din enunt. Urmeaza M linii care contin cate doua numere A si B cu semnificatia ca exista o poteca de la casa A la casa B.

Date de iesire

Pe prima linie a fisierului de iesire strazi.out se afla numarul MIN care reprezinta numarul minim de poteci ce trebuie construite. Urmeaza apoi MIN linii, fiecare continand cate doua numere X si Y cu semnificatia ca s-a construit o poteca de la casa X la casa Y. Pe ultima linie a fisierului se afla N numere naturale distincte cu valori intre 1 si N, reprezentand un traseu pe care oaspetii l-ar putea urma.

Restrictii

  • 1 ≤ N ≤ 255
  • 1 ≤ M ≤ 7000
  • Daca exista mai multe solutii posibile, se poate afisa oricare
  • Pentru cel putin 20% din teste N ≤ 10

Exemplu

strazi.instrazi.out
3 2
1 2
1 3
1
2 3
1 2 3

Explicatie

Daca se construieste poteca de la 2 la 3 se pot vizita in ordine casele 1, 2 si 3, intre doua case consecutive existand o poteca ce le leaga.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content