Fișierul intrare/ieșire | coborare.in, coborare.out | Sursă | ad-hoc |
---|---|---|---|
Autor | clasică | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.4 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Coborâre (clasele 11-12)
Un turist a făcut o excursie până în vârful unui munte. Acum, el dorește să coboare înapoi la cabană. Muntele este presărat cu poieni între care se află cărări. Fiecare cărare leagă două poieni diferite, iar într-o poiană pot ajunge mai multe cărări. Turistul se întreabă: câte trasee diferite există din vârful muntelui la cabană, care să meargă numai pe cărări și numai la vale?
Date de intrare
Fișierul de intrare coborare.in conține pe prima linie patru numere N M V C, unde
- N este numărul de poieni;
- M este numărul de cărări;
- V este poiana din vârful muntelui (de unde pornește turistul);
- C este poiana în care se află cabana.
Pe următoarele M linii se află câte o pereche de numere x y, cu semnificația că există o cărare care coboară din poiana x în poiana y.
Date de ieșire
În fișierul de ieșire coborare.out se va scrie un singur număr, respectiv numărul de trasee distincte de la V la C, modulo 100003.
Restricții
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 300.000
- 1 ≤ V, C ≤ N
- Poienile au numere între 1 și N.
Exemplu
coborare.in | coborare.out |
---|---|
6 8 3 4 3 2 2 1 1 6 6 4 4 5 3 1 1 4 2 6 |
5 |
Explicație
Cele 5 drumuri sunt 3-2-1-6-4-5, 3-2-1-4-5, 3-2-6-4-5, 3-1-6-4-5 și 3-1-4-5.