== include(page="template/taskheader" task_id="shgraf") ==
Poveste şi cerinţă...
Miruna a devenit de curând fascinată de grafuri. Mirunei i-au plăcut grafurile atât de tare, încât s-a decis să inventeze o nouă proprietate a lor. Astfel, ea consideră că un graf neorientat simplu are proprietatea de $„SHGRAF”$ dacă şi numai dacă se respectă una dintre următoarele două cerinţe:
* Este un graf conex în care numărul de noduri este egal cu numărul de muchii.
* Nu este un graf conex, dar fiecare componentă conexă a sa are proprietatea de $„SHGRAF”$.
Prietena cea mai bună a Mirunei, A. Irina, este o fire foarte curioasă. Ea s-a gândit la două numere naturale $N$ şi $K$, iar acum o întreabă pe Miruna câte grafuri etichetate cu $N$ noduri şi cu proprietatea de $„SHGRAF”$ există, astfel încât orice ciclu din graf are lungimea mai mare sau egală decât $K$.
h2. Cerinţa
Ajutaţi-o pe Miruna să răspundă provocării A. Irinei, scriind un program care sa afişeze numărul căutat modulo $30011$.
h2. Date de intrare
Fişierul de intrare $shgraf.in$ ...
Fişierul de intrare $shgraf.in$ conţine pe prima linie două numere naturale $N$ şi $K$, având semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $shgraf.out$ ...
Fişierul de ieşire $shgraf.out$ va conţine o singură linie pe care va fi afişat un număr întreg, reprezentând numărul total de grafuri etichetate cu $N$ noduri, fără cicluri de lungime mai mică decât $K$ şi care au proprietatea de $„SHGRAF”$, modulo $30011$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 250$
* $3 ≤ K ≤ N$
* Pentru $40%$ din teste $3 ≤ N ≤ 50$
h2. Exemplu
table(example). |_. shgraf.in |_. shgraf.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3 3
| 1 |
| 50 10
| 20726
|
h3. Explicaţie
...
# Singurul graf care respectă condiţiile impuse este ciclul elementar format din 3 noduri.
# Numărul de grafuri este prea mare pentru mai multe explicaţii, va trebui să ne credeţi pe cuvânt ;)
== include(page="template/taskfooter" task_id="shgraf") ==
