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)