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