Fişierul intrare/ieşire:coborare.in, coborare.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.4 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.incoborare.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 sa te autentifici pentru a trimite solutii. Click aici