| 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 Luminoasa. In padure exista N luminisuri (pentru simplitate vom considera ca initial 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 fetita, ea va vizita cel putin 4 luminisuri pentru a ajunge la casa bunicii (incluzand luminisurile 1 si N).
Pentru a o ajuta pe Scufita sa nu se rataceasca, Padurarul cel Viteaz vrea sa amenajeze cat mai multe poteci noi prin padure, dar vrea sa construiasca potecile in asa fel incat orice drum ar alege fetita, ea sa viziteze cel putin 4 luminisuri.
Ajutati-l pe padurar sa creeze un numar maxim de noi poteci astfel incat mergand prin padure, Scufita sa viziteze cel putin 4 luminisuri.
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
- Vom considera ca doua poteci se vor intersecta doar intr-un luminis.
- Intre doua luminisuri va exista cel mult o poteca.
- Stim ca Scufita poate sa ajunga la casa bunicii folosind cele M poteci initiale.
Exemplu
| dmin2.in | dmin2.out |
|---|---|
| 5 3 1 2 2 3 3 5 | 3 |
Explicaţie
Padurarul va amenaja poteci intre 2 si 4, 3 si 4 si 4 si 5.
