| Fişierul intrare/ieşire: | strazi.in, strazi.out | Sursă | preONI 2008 Runda 3 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | strazi.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.
