CSES - Datatähti 2020 loppu - Kierrokset
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Bittimaassa on nn kaupunkia ja niiden välillä n1n-1 tietä. Jokaisen kahden kaupungin välillä on jokin reitti.

Tehtäväsi on suunnitella turistikierros, joka alkaa kaupungista xx, kulkee teitä pitkin ja päättyy kaupunkiin yy. Kaksi kierrosta ovat erilaiset, jos on jokin kaupunki, jossa käyt vain toisessa kierroksista.

Montako erilaista turistikierrosta voit suunnitella?

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua nn, xx ja yy. Kaupungit on numeroitu 1,2,,n1,2,\dots,n.

Seuraavat n1n-1 riviä kuvaavat tiet. Kullakin rivillä on kaksi kokonaislukua aa ja bb: kaupunkien aa ja bb välillä on tie.

Tuloste

Tulosta yksi kokonaisluku: erilaisten turistikierrosten määrä. Koska vastaus voi olla suuri, tulosta se modulo 109+710^9+7.

Esimerkki

Syöte:

7 2 5
2 7
5 7
2 1
5 3
2 6
4 5

Tuloste:

16

Osatehtävä 1 (22 pistettä)

  • 1n101 \leq n \leq 10

Osatehtävä 2 (25 pistettä)

  • 1n21051 \leq n \leq 2 \cdot 10^5
  • kustakin kaupungista lähtee enintään kaksi tietä

Osatehtävä 3 (26 pistettä)

  • 1n21051 \leq n \leq 2 \cdot 10^5
  • x=yx = y, eli kierros alkaa ja päättyy samassa kaupungissa

Osatehtävä 4 (27 pistettä)

  • 1n21051 \leq n \leq 2 \cdot 10^5