Under construction

Still being built. Things may change

Counting four cycles

Interview

Time limit2sMemory limit128 MB

Summary
Count ordered 4-vertex cycles in an undirected graph given as an N by N adjacency matrix with N up to 250.
Level

Medium5 of 10

Topics
Graph, Combinatorics, Matrix
Solved
No attempts yet

Problem

You are given an undirected graph. Count the four cycles it contains.

A four cycle is a cycle of length 4 on four distinct vertices. Vertices v1,v2,v3,v4v_1, v_2, v_3, v_4 in this order form one when they are pairwise distinct and v1v2v_1 v_2, v2v3v_2 v_3, v3v4v_3 v_4, v4v1v_4 v_1 are all edges.

Orders that visit the vertices differently count as different four cycles. For example, 1 -> 2 -> 3 -> 4 -> 1 and 2 -> 3 -> 4 -> 1 -> 2 are counted separately.

Input

The first line has the number of vertices NN. (1≤N≤2501 \le N \le 250)

Each of the next NN lines holds one row of the adjacency matrix AA of the undirected graph, given as NN integers separated by spaces, each of them 0 or 1. AijA_{ij} is 1 when an edge joins vertex ii and vertex jj, and 0 when it does not. No AiiA_{ii} is 1.

Output

Print the number of four cycles on one line.

Examples4

  1. Example 1

    Input
    4
    0 1 0 1
    1 0 1 0
    0 1 0 1
    1 0 1 0
    
    Expected output
    8
    
  2. Example 2

    Input
    4
    0 1 1 1
    1 0 1 1
    1 1 0 1
    1 1 1 0
    
    Expected output
    24
    
  3. Example 3

    Input
    6
    0 0 0 1 1 1
    0 0 0 1 1 1
    0 0 0 1 1 1
    1 1 1 0 0 0
    1 1 1 0 0 0
    1 1 1 0 0 0
    
    Expected output
    72
    
  4. Example 4

    Input
    10
    0 0 0 1 1 1 0 0 0 0
    0 0 0 0 1 0 1 1 1 0
    0 0 0 1 0 0 1 1 1 0
    1 0 1 0 1 1 0 1 1 1
    1 1 0 1 0 1 1 1 0 0
    1 0 0 1 1 0 0 0 1 1
    0 1 1 0 1 0 0 0 1 0
    0 1 1 1 1 0 0 0 1 0
    0 1 1 1 0 1 1 1 0 1
    0 0 0 1 0 1 0 0 1 0
    
    Expected output
    320