Je to tu – obdobie extrémnej nákupovej mánie. Zľavy na zľavy, čierne piatky, kybernetické pondelky, mikulášske akcie… Škoda len, že sa nám tento rok minuli aj rozprávky k zadaniam, vypredali sa dokonca ešte rýchlejšie ako RAMky v zľave. Budete si teda musieť vystačiť len s holou úlohou:

Úloha

Máme zadaný neorientovaný graf $G$, kde každý vrchol má stupeň¹ najviac $d \leq 16$. Klika v grafe je taká podmnožina vrcholov, v ktorej je každá dvojica vrcholov spojená. Nájdite počet klík veľkosti $k$ v grafe $G$. Dve kliky počítame ako rôzne ak sa líšia v aspoň jednom vrchole.

Formát vstupu

V prvom riadku vstupu sú čísla $n, m, k$ udávajúce počet vrcholov grafu $G$, počet hrán grafu $G$, a veľkosť klík, ktoré chceme hľadať.

Nasleduje $m$ riadkov, na každom sú dve čísla $a_i, b_i$ ($0 \leq a_i, b_i < n$) popisujúce hrany grafu. Je garantované, že graf neobsahuje slučky a násobné hrany.

Označme $d$ maximálny stupeň vrchola v grafe $G$. V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jeden riadok a v ňom jedno číslo udávajúce počet klík veľkosti presne $k$, ktoré sa nachádzajú v grafe.

Príklady

4 5 3
0 1
1 2
2 0
0 3
1 3

2

Graf obsahuje dve kliky veľkosti tri. Tie sú zložené z vrcholov {0, 1, 2} a {0, 1, 3}.

4 4 4
0 1
1 2
2 3
3 0

0

Graf neobsahuje žiadnu kliku veľkosti 4, lebo neobsahuje hrany (0, 2) a (1, 3).