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.