- Time limit: 1.00 s
- Memory limit: 512 MB
Tehtäväsi on suunnitella turistikierros, joka alkaa kaupungista $x$, kulkee teitä pitkin ja päättyy kaupunkiin $y$. 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 $n$, $x$ ja $y$. Kaupungit on numeroitu $1,2,\dots,n$.
Seuraavat $n-1$ riviä kuvaavat tiet. Kullakin rivillä on kaksi kokonaislukua $a$ ja $b$: kaupunkien $a$ ja $b$ välillä on tie.
Tuloste
Tulosta yksi kokonaisluku: erilaisten turistikierrosten määrä. Koska vastaus voi olla suuri, tulosta se modulo $10^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ä)
- $1 \leq n \leq 10$
- $1 \leq n \leq 2 \cdot 10^5$
- kustakin kaupungista lähtee enintään kaksi tietä
- $1 \leq n \leq 2 \cdot 10^5$
- $x = y$, eli kierros alkaa ja päättyy samassa kaupungissa
- $1 \leq n \leq 2 \cdot 10^5$