nkgraf

Fie $N, K, P$ trei numere naturale nenule. Vom considera toate grafurile orientate care au $N$ vârfuri şi $K$ arce, reprezentate prin lista arcelor lor ordonate lexicografic.
Vom ordona apoi grafurile lexicografic şi le vom numerota începând cu $1$.

Cerinţă

Scrieţi un program care, cunoscând $N$, $K$ şi $P$, rezolvă următoarele două cerinţe:

1. determină $NR$, numărul de grafuri orientate cu $N$ vârfuri şi $K$ arce;
2. determină graful orientat cu $N$ vârfuri şi $K$ arce având numărul de ordine $P$.

Date de intrare

Fişierul de intrare nkgraf.in conţine pe prima linie cerinţa care trebuie să fie rezolvată ($1$ sau $2$). Pe a doua linie se află trei numere naturale separate prin câte-un spaţiu $N \ K \ P$, având semnificaţia din enunţ.

Date de ieşire

Dacă cerinţa este $1$, fişierul de ieşire nkgraf.out va conţine o singură linie pe care va fi scris $NR$, numărul de grafuri orientate cu $N$ vârfuri şi $K$ arce.
Dacă cerinţa este $2$, fişierul de ieşire nkgraf.out va conţine $K$ linii pe care vor fi scrise în ordine lexicografică cele $K$ arce ale grafului având numărul de ordine $P$, câte un arc pe o linie; pentru fiecare arc vor fi scrise două vârfuri separate printr-un spaţiu, reprezentând extremitatea iniţială şi respectiv extremitatea finală a arcului.

Restricții și precizări

• $2 \leq N \leq 30$
• $1 \leq P \leq min (NR,10^6)$
• Orice arc din graf va avea extremitatea iniţială diferită de extremitatea finală.
• Pentru teste valorând $30$ de puncte cerinţa este $1$ şi $N \leq 8$.
• Pentru teste valorând $30$ de puncte cerinţa este $1$ şi $8 < N \leq 30$.
• Pentru teste valorând $30$ de puncte cerinţa este $2$.
• $10$ puncte se acordă din oficiu.

Exemplul 1

nkgraf.in

1
3 2 6

nkgraf.out

15

Exemplul 2

nkgraf.in

2
3 2 6

nkgraf.out

1 3
2 1

Explicații

Există $15$ grafuri cu $3$ vârfuri şi două arce. În ordine lexicografică acestea sunt: