Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Asteet


Task | Statistics


CSES - AsteetCSES - 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
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.