- Time limit: 3.00 s
- Memory limit: 512 MB
Eulerinen aliverkko on sellainen osajoukko verkon kaarista että jokaisen solmun aste on parillinen. Tehtävänäsi on laskea verkon euleristen aliverkkojen kokojen neliöiden summa modulo . Eulerisen aliverkon koko on siinä olevien kaarien määrä.
Syöte
Ensimmäisellä rivillä on kaksi lukua, ja , verkon solmujen ja kaarien määrä. Seuraavalla :llä rivillä on jokaisella kaksi lukua, ja , jotka tarkoittavat että verkossa on kaari solmujen ja välillä. Verkossa voi olla kaaria solmusta itseensä (tällöin molemmat päät nostavat solmun astelukua) ja verkossa voi olla useampia kaaria saman solmuparin välillä.
Tuloste
Tulosta yksi luku, euleristen aliverkkojen kokojen neliöiden summa modulo .
Rajat
Esimerkki
Syöte:
4 4 1 2 1 3 1 4 2 3
Tuloste:
9
Syöte:
6 6 1 2 2 3 3 1 4 5 5 6 6 4
Tuloste:
54
Syöte:
2 3 1 1 1 2 1 2
Tuloste:
14
Syöte:
1 1 1 1
Tuloste:
1