| Fişierul intrare/ieşire: | bip.in, bip.out | Sursă | Tuymaada 2022 |
| Autor | Alexandru Petrescu | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bip
Se da un graf conex si neorientat. Sa se taie o muchie in asa fel incat el sa devina bipartit (conex sau nu).
Date de intrare
Fişierul de intrare bip.in contine, pe prima linie, numarul T de teste, apoi liniile care descriu fiecare test in parte, astfel:
- pe prima linie, numerele N de noduri si M de muchii, despartite prin cate un spatiu
- pe urmatoarele M linii, muchiile cu indicii 0, 1, ..., M-1 descrise prin cate o pereche neordonata de numere despartite printr-un spatiu, reprezentand nodurile
Se garanteaza ca muchiile nu se repeta si ca, initial, graful nu e bipartit.
Date de ieşire
În fişierul de ieşire bip.out se afla T descrieri ale raspunsului pentru fiecare test, astfel:
- pe prima linie, numarul de muchii pe care le putem elimina astfel incat graful sa devina bipartit; daca acesta e nenul,
- pe a doua linie, indicii acestor muchii, in ordine crescatoare si despartiti prin cate un spatiu
Restricţii
Fie Q suma numerelor M din cele T teste.
- 3 ≤ N ≤ M ≤ 50.000
- Q ≤ 150.000
- Pentru 20 de puncte, Q ≤ 500
- Pentru inca 10 de puncte, graful contine un singur ciclu
- Pentru inca 40 de puncte, Q ≤ 30.000
Exemplu
| bip.in | bip.out |
|---|---|
| 3 3 3 1 2 2 3 3 1 4 6 1 2 1 3 1 4 2 3 2 4 3 4 7 8 1 2 2 3 3 4 4 5 5 6 6 7 6 3 7 1 | 3 0 1 2 0 4 0 1 5 7 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
