Se da un graf orientat aciclic cu n noduri si m muchii orientate, si doua noduri a si b. Determinati numarul de drumuri orientate distincte de la a la b (drumul de lungime 0, daca a = b, se numara ca 1 drum).
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii cu cate o muchie orientata. Pe ultima linie se citesc a si b.
- Date de iesire
- Se afiseaza numarul de drumuri distincte de la a la b.
- Restrictii
- 1 <= n <= 100000, 0 <= m <= 200000, graful este garantat DAG, raspunsul incape pe 64 de biti
Exemple
Exemplul 1
Intrare
4 4 1 2 1 3 2 4 3 4 1 4
Iesire
2
Exemplul 2
Intrare
4 3 1 2 2 3 3 4 1 4
Iesire
1