Fișierul intrare/ieșire coborare.in, coborare.out Sursă ad-hoc
Autor clasică Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii