CSES - Asteet
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Annettuna on suuntaamaton verkko, jossa on $n$ solmua ja $m$ kaarta.

Monellako tavalla voit poistaa verkosta jonkin osajoukon kaaria niin, että jokaisen solmun aste (eli solmun naapurien määrä) on parillinen?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: solmujen määrä ja kaarten määrä. Solmut on numeroitu kokonaisluvuin $1,2,\dots,n$.

Seuraavat $m$ riviä kuvaavat kaaret. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: solmujen $a$ ja $b$ välillä on kaari. Sama kaari ei esiinny monta kertaa verkossa.

Tuloste

Tulosta yksi kokonaisluku: tapojen määrä modulo $10^9+7$.

Rajat
  • $1 \le n \le 2 \cdot 10^5$
  • $1 \le m \le 5 \cdot 10^5$
Esimerkki

Syöte:
4 5
1 2
1 3
2 3
2 4
3 4


Tuloste:
4

Selitys: Voit poistaa kaaren $(2,3)$, kaaret $(1,2)$ ja $(1,3)$, kaaret $(2,3)$ ja $(2,4)$ tai kaikki kaaret.