Fişierul intrare/ieşire:bip.in, bip.outSursăTuymaada 2022
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu alexpetrescu
Timp execuţie pe test0.3 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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.inbip.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

Cum se trimit solutii?