Fişierul intrare/ieşire:	negustori.in, negustori.out	Sursă	Summer Challenge 2009, Runda 3
Autor	Din Folclor	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	0.125 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Negustori

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ă.

Date de intrare

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₁, b₁, ..., 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ă.

Date de ieşire

Î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).

Restricţii

• 1 ≤ n ≤ 300
• 0 ≤ m ≤ n
• 2 ≤ M ≤ 10⁹

Exemplu

Explicaţie

Este exemplul din enunţ.

Cum se trimit solutii?