== include(page="template/taskheader" task_id="negustori") ==
Poveste şi cerinţă...
Sunteţi santinela unei bresle de negustori. Astăzi dimineaţă, $n$ negustori (numerotaţi de la $1$ la $n$) s-au aşezat în linie pentru a intra pe aleea comercială a oraşului. De-alungul aleii există $n$ locaţii unde negustorii îşi pot parca căruţele pentru a-şi vinde ulterior bunurile. Începând cu negustorul numărul $1$, fiecare negustor, unul după celălalt, intră pe alee cu căruţa proprie, se îndreaptă către locaţia repartizată iar dacă este liberă o ocupă. Altfel, negustorul îşi continuă drumul spre următorul loc liber pe care îl ocupă. Dacă toate următoarele locaţii sunt ocupate, acesta părăseşte oraşul fără a-şi vinde bunurile.
Negustorii nu îşi pot întoarce căruţele datorită îngustimii aleii. Sarcina dvs ca santinelă este să repartizaţi negustorii în locaţiile de pe alee. Negustorii locali sunt privilegiaţi în sensul că sunt repartizaţi în locaţia favorită, în timp ce negustorii străini vor trebui să accepte orice locaţie le desemnaţi.
Fiind date locaţiile preferate ale negustorilor locali, trebuie să decideţi dacă există o repartizare a negustorilor străini în locaţii de pe alee astfel încât fiecare negustor (deopotrivă local şi străin) să îşi găsească un loc liber. În caz că există o astfel de repartizare, trebuie să găsiţi numărul de repartizări valide modulo un număr întreg dat $M$.
Să considerăm un exemplu. Să presupunem că există patru negustori. Primii trei sunt negustori locali cu poziţia favorită $2$, $1$, respectiv $1$. Ultimul negustor este străin. Fiecare negustor îşi găseşte un loc liber în fiecare din următoarele patru cazuri: $(2, 1, 1, 1)$, $(2, 1, 1, 2)$, $(2, 1, 1, 3)$, $(2, 1, 1, 4)$, unde, de exemplu, $(2, 1, 1, 3)$ înseamnă că primul negustor are repartizată poziţia $2$, ... , iar ultimul negustor poziţia $3$. Acest exemplu arată că negustori locali diferiţi pot avea locaţii favorite identice, că unui negustor străin i se poate repartizata o locaţie dorită de un negustor local şi că locaţia finală a unui negustor local poate fi îndepărtată de locaţia favorită.
h2. Date de intrare
Fişierul de intrare $negustori.in$ ...
Fişierul de intrare $negustori.in$ conţine pe prima linie trei numere întregi $n$, $m$, $M$, separate prin spaţiu, unde $m$ reprezintă numărul negustorilor locali din toţi cei $n$ negustori. Pe următoarea linie se vor găsi $m$ perechi de numere $a{~1~}, b{~1~}, ..., a{~m~}, b{~m~}$, cu $1 ≤ a{~i~}, b{~i~} ≤ n$ şi toţi $a{~i~}$ diferiţi, unde $a{~i~}$ este poziţia celui de al $i$-lea negustor local în coadă iar $b{~i~}$ locaţia sa preferată. Dacă nu există negustori locali, această linie va fi goală.
h2. Date de ieşire
În fişierul de ieşire $negustori.out$ ...
În fişierul de ieşire $negustori.out$ se va scrie o singură linie, conţinând, fie $NO$ dacă este imposibil ca fiecare negustor să primească o locaţie liberă, fie $YES$ urmat de numărul total de repartizări modulo $M$ (separate printr-un spaţiu).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 300$
* $0 ≤ m ≤ n$
* $2 ≤ M ≤ 10^9^$
h2. Exemplu
table(example). |_. negustori.in |_. negustori.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 3 10
1 2 2 1 3 1
|YES 4
|
h3. Explicaţie
...
Este exemplul din enunţ.
== include(page="template/taskfooter" task_id="negustori") ==
