Zadanie

Four-cliques

Počet bodov: 50, časový limit: 2600ms

Daný je jednoduchý neorientovaný graf.

Koľko je v ňom rôznych 4-klík?

Vstup a výstup

V prvom riadku je číslo \(n\): počet vrcholov grafu. Vrcholy číslujeme od \(0\) po \(n-1\). Nasleduje \(n\) riadkov, \(i\)-ty z nich obsahuje medzerou oddelené čísla vrcholov, ktoré sú spojené hranou s vrcholom \(i\).

Keďže sme boli leniví, grafy sme vygenerovali náhodne: každá hrana sa v grafe vyskytuje s pravdepodobnostou \(\frac{ln(n)}{\sqrt{n}}\). Vygenerovali sme ich v pythone nasledovne:

from random import *
from math import log
seed(n)
hranica = log(n) / (n ** 0.5)
for i in range(n):
    for k in range(i+1,n):
        r = random()
        if r <= hranica:
            # existuje hrana medzi vrcholmi i a k

Vypíšte jedno číslo: počet 4-klík v danom grafe. 4-klika ja štvorica vrcholov takých, že medzi každou dvojicou z nich existuje hrana. Dve kliky považujeme za rôzne, ak sa neskladajú z tých istých štyroch vrcholov.

Vo vstupoch sa práve raz vyskytujú všetky \(n\) v tvare \(k10^1\) a \(k10^2\) pre \(1 \leq k \leq 60\).

Ešte malá prosbička: k tejto úlohe máte full feedback, a je veľa vstupov. Prosím skúste odovzdávať pomenej programov.

Príklad

Input:

10
1 2 3 4 7 8 9
0 2 3 6 8 9
0 1 3 4 5 6 7 8
0 1 2 6 7 8 9
0 2 6 7 9
2 6 7 8 9
1 2 3 4 5 8 9
0 2 3 4 5 8 9
0 1 2 3 5 6 7 9
0 1 3 4 5 6 7 8

Output:

29