Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dmin2.in, dmin2.out | Sursă | Algoritmiada 2013, Runda 2 |
| Autor | Andrei Grigorean | Adăugată de |  Mihai Gheorghe •GheorgheMihai |
| Timp execuţie pe test | 0.035 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dmin2
Pentru a ajunge la casa bunicii, Scufita Rosie trebuie sa traverseze Padurea Bucuroasa. In padure exista N luminisuri (pentru simplitate vom considera ca Scufita Rosie este in luminisul 1 si casa bunicii este in luminisul N). Luminisurile sunt legate intre ele prin M poteci, iar Scufita se poate deplasa doar pe poteci si prin luminisuri (altfel o va manca Lupul cel Mare si Rau). Stim ca orice drum ar alege Scufita, ea va vizita cel putin 4 luminisuri pentru a ajunge la casa bunicii (incluzand luminisurile 1 si N).
Pentru a o ajuta pe Scufita, Padurarul cel Viteaz vrea sa faca cat mai multe poteci noi prin padure astfel incat Scufita sa ajunga cat mai repede la casa bunicii, dar totusi vrea ca orice drum ar alege aceasta, sa viziteze cel putin 4 poieni (altfel fetita ar manca din prajiturile bunicii si nu ar mai admira frumusetile padurii).
Ajutati-l pe padurar sa creeze un numar maxim de noi poteci astfel incat mergand prin padure, Scufita sa viziteze cel putin 4 poieni.
Date de intrare
Fişierul de intrare dmin2.in contine pe prima linie numarul doua numere naturale N si M cu semnificatia din enunt. Pe fiecare dintre urmatoarele M linii se va gasi cate o pereche de numere x si y cu semnificatia ca exista o poteca intre poiana x si poiana y.
Date de ieşire
În fişierul de ieşire dmin2.out scrieti numarul maxim de poteci pe care le poate amenaja padurarul!
Restricţii
- 1 ≤ N ≤ 100000
- 1 ≤ M ≤ 300000
Exemplu
| dmin2.in | dmin2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
