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.

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ța

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 ≤ N ≤ 30
• 1 ≤ P ≤ min {NR,1.000.000}
• Orice arc din graf a avea extremitatea iniţială diferită de extremitatea finală.

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ție

Există 15 grafuri cu 3 vârfuri şi două arce. În ordine lexicografică acestea sunt:
Graf 1: (1,2), (1,3)
Graf 2: (1,2), (2,1)
Graf 3: (1,2), (2,3)
Graf 4: (1,2), (3,1)
Graf 5: (1,2), (3,2)
Graf 6: (1,3), (2,1)
Graf 7: (1,3), (2,3)
Graf 8: (1,3), (3,1)
Graf 9: (1,3), (3,2)
Graf 10: (2,1), (2,3)
Graf 11: (2,1), (3,1)
Graf 12: (2,1), (3,2)
Graf 13: (2,3), (3,1)
Graf 14: (2,3), (3,2)
Graf 15: (3,1), (3,2)

#include <bits/stdc++.h>
using namespace std;

ifstream cin("nkgraf.in");
ofstream cout("nkgraf.out");

int cer , n , k , p , v[1001] , x[1001], r[1001];

void comb(int n , int k)
{
    for(int i = 1 ; i <= k ; i++)
        v[i] = n - i + 1;
    for(int i = 1 ; i <= k ; i++)
    {
        int x = i , d = 2;
        while(x > 1)
        {
            if(x % d == 0)
            {
                int p = 0;
                for(int j = 1 ; j <= k ; j++)
                    if(v[j] % d == 0) p = j;
                v[p] /= d;
                x /= d;
            }
            else d++;
            if(d * d > x) d = x;
        }
    }
    int r[1001];
    r[0] = 1 , r[1] = 1;
    for(int i = 1 ; i <= k ; i++)
    {
        int t = 0;
        for(int j = 1 ; j <= r[0] ; j++)
        {
            int x = t + r[j] * v[i];
            r[j] = x % 10;
            t = x / 10;
        }
        while(t) r[++r[0]] = t % 10 , t /=10;
    }
    for(int i = r[0] ; i > 0 ; i--)
        cout << r[i];
}

void afisare()
{
    for(int i =1 ; i <= n * n-n ; i ++)
        r[i] = 0;
    for(int i =1 ; i <= k ; i ++)
        r[x[i]] = 1;
    int q = 0;
        for(int i =1 ; i <= n ; i ++)
            for(int j =1 ; j <= n ; j ++)
                if(i != j)
                    if(r[++q] == 1) cout << i << " " << j << "\n";
}

void back(int q)
{
    for(int i = x[q-1] + 1; p > 0 &&  i <= n * (n-1) ; i ++)
    {
        x[q]  = i;
        if(q == k)
        {
            p--;
            if(p == 0) afisare();
        }
        else back(q + 1);
    }
}

int main()
{
    cin >> cer >> n >> k >> p;
    if(cer == 1) comb(n * (n - 1) , k);
    else back(1);
}