CSES - Jalkapallo
  • Time limit: 3.00 s
  • Memory limit: 512 MB

Syrjälän asukkaat pelaavat usein jalkapalloa keskenään. Peliä varten asukkaat jaetaan kahteen joukkueeseen. Kuitenkin aina joskus kaksi asukasta riitaantuvat keskenään, eivätkä halua enää ikinä pelata samassa joukkueessa. Kun annetaan lista tapahtumista muotoa "asukas a riitaantui asukkaan b kanssa", selvitä jokaisen tapahtuman jälkeen kuinka monella tavalla asukkaat voidaan jakaa kahteen joukkueeseen. Ilmoita vastaus modulo 10^9+7.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua, n ja m, asukkaiden määrä ja tapahtumien määrä. Seuraavilla m:llä rivillä on jokaisella kaksi lukua a_i ja b_i, jotka tarkoittavat että asukas a_i riitaantui asukkaan b_i kanssa.

Tuloste

Tulosta m lukua, kuinka monella tavalla asukkaat voidaan jakaa kahteen joukkueeseen jokaisen tapahtuman jälkeen modulo 10^9+7.

Rajat

  • 2 \le n \le 10^5
  • 1 \le m \le 2 \cdot 10^5
  • 1 \le a_i, b_i \le n, a_i \neq b_i

Esimerkki

Syöte:

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

Tuloste:

8
4
2
1
1
0