사각형 세기

N이 최대 250인 무향 그래프의 인접 행렬이 주어질 때 시작점과 방향이 다른 경우를 구분하여 길이가 4인 사이클 개수를 구합니다.

보통5그래프조합론행렬면접 대비아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제

무방향 그래프가 주어진다. 이 그래프에 들어 있는 사각형의 개수를 세어라.

사각형은 서로 다른 네 정점으로 이루어진 길이 4인 사이클이다. 정점 v1,v2,v3,v4v_1, v_2, v_3, v_4가 모두 다르고 v1v2v_1 v_2, v2v3v_2 v_3, v3v4v_3 v_4, v4v1v_4 v_1이 모두 간선이면 이 순서가 사각형 하나가 된다.

정점을 방문하는 순서가 다르면 다른 사각형으로 센다. 예를 들어 1 -> 2 -> 3 -> 4 -> 1과 2 -> 3 -> 4 -> 1 -> 2는 따로 센다.

입력

첫째 줄에 정점의 개수 NN이 주어진다. (1N2501 \le N \le 250)

다음 NN개의 줄에는 무방향 그래프의 인접행렬 AA가 주어진다. 각 줄에는 0 또는 1인 정수가 NN개씩 공백으로 구분되어 들어 있다. 정점 ii와 정점 jj를 잇는 간선이 있으면 AijA_{ij}가 1이고, 없으면 0이다. AiiA_{ii}가 1인 경우는 없다.

출력

사각형의 개수를 한 줄에 출력한다.