Fişierul intrare/ieşire:ratway.in, ratway.outSursăInfoOltenia 2018 - Clasele 11 - 12
AutorBogdan IordacheAdăugată deinfoolteniaInfo-Oltenia 2018 infooltenia
Timp execuţie pe test2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ratway

"You could say the Ratway is the city under the city. Dark, dangerous, and no place for decent folk."

Cetatea Riften din provincia Skyrim este cunoscută pentru reţeaua subterană de tuneluri, supranumită "The Ratway". Această reţea este alcătuită din tuneluri bidirecţionale şi intersecţii de tuneluri, astfel poate fi reprezentată printr-un multigraf neorientat conex (fiecărei intersecţii i se asociază un nod, iar fiecărui tunel i se asociază o muchie între nodurile corespunzătoare, pot exista muchii multiple între aceleaşi noduri şi pot exista muchii de la un nod la el însuşi).

Ratway-ul conţine şi sediul ghildei tâlharilor din Skyrim. Brynjolf, unul din liderii acesteia, doreşte să dezvolte un nou sistem de capcane pentru a ţine departe gărzile, dar mai întâi reţeaua de tuneluri trebuie să respecte câteva restricţii: tunelurile trebuie sa fie orientate (se pot parcurge într-un singur sens, altfel s-ar activa capcanele), pentru orice intersecţie atât numărul de intrări, cât şi cel de ieşiri trebuie să fie numere pare (prin intrare se înţelege un tunel orientat de la o intersecţie oarecare la intersecţia curentă, iar prin ieşire se înţelege un tunel orientat de la intersecţia curentă la o intersecţie oarecare).

Ajutaţi-l pe Brynjolf să orienteze tunelurile pentru a respecta restricţiile de mai sus. Dacă nu este posibil, construiţi un număr minim de tuneluri, pe care de asemenea să le orientaţi astfel încât reţeaua rezultată să respecte restricţiile.

Date de intrare

Prima linie a fişierului ratway.in va conţine două numere naturale N şi M, reprezentând numărul de intersecţii şi numărul de tuneluri iniţiale.
Pe fiecare dintre următoarele M linii, se vor găsi două numere naturale, x şi y, cu semnificaţia că există tunel între intersecţiile x şi y (intersecţiile sunt reprezentate prin numere naturale de la 1 la N).

Date de ieşire

Pe prima linie a fişierului ratway.out afişaţi K, numărul minim de tuneluri din reţeaua finală.
Pe fiecare din următoarele K linii afişaţi câte două numere, x şi y, semnificând că avem un tunel orientat de la nodul x la nodul y. Printre tunelurile afişate, trebuie să se afle şi tunelurile din configuraţia iniţială, unde fiecăruia i-a fost atribuită exact una din cele două direcţii posibile.
Dacă există mai multe soluţii cu K minim, afişaţi pe oricare dintre acestea.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 200.000
  • pentru 15% din punctaj 1 ≤ M ≤ 20 şi nu trebuie construite tuneluri suplimentare
  • pentru alte 30% din punctaj 1 ≤ N ≤ 1000, 1 ≤ M ≤ 2000

Exemplu

ratway.inratway.out
3 4
1 2
2 3
1 1
3 3
6
1 1
2 1
2 3
3 3
3 1
1 1

Explicaţie

Muchiile din fişierul de intrare se orientează astfel: 1<-2,2->3,1->1,3->3.
Se mai adaugă tuneluri orientate: 3->1, 1->1.
Pentru nodul 1 avem: 4 intrări, 2 ieşiri.
Pentru nodul 2 avem: 0 intrări, 2 ieşiri.
Pentru nodul 3 avem: 2 intrări, 2 ieşiri.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?