CSES - Sillat
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Saat syötteenä verkon jossa on n solmua ja m kaarta. Tehtäväsi on löytää kaaret joiden poistaminen kasvattaa verkon yhtenäisten komponenttien määrää.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua, n ja m, verkon solmujen ja kaarien määrä. Seuraavilla m:llä rivillä on jokaisella luvut u ja v, jotka tarkoittavat että solmujen u ja v välillä on kaari. Kahden solmun välillä on korkeintaan yksi kaari.

Tuloste

Tulosta ensimmäiselle riville luku k, eli sellaisten kaarien määrä, joiden poistaminen kasvattaa verkon yhtenäisten komponenttien määrää. Tulosta sen jälkeen k riviä, joista jokaisella on yhden kaaren kuvaus syötteen tapaisesti. Voit tulostaa kaaret missä järjestyksessä tahansa.

Rajat

  • 2 \le n \le 2 \cdot 10^5
  • 1 \le m \le 5 \cdot 10^5
  • 1 \le u, v \le n, u \neq v

Esimerkki

Syöte:

6 7
1 2
2 5
2 6
5 6
1 4
1 3
3 4

Tuloste:

1
1 2

Syöte:

10 13
1 2
10 1
2 3
2 9
9 10
9 8
9 7
7 8
2 8
3 5
3 4
4 5
5 6

Tuloste:

2
2 3
6 5