Square in a Graph solved by 456

Problem

Given: A positive integer $k \le 20$ and $k$ simple undirected graphs with $n \le 400$ vertices in the edge list format.

Return: For each graph, output "1" if it contains a simple cycle (that is, a cycle which doesn’t intersect itself) of length $4$ and "-1" otherwise.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Sample Dataset

2

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

4 4
1 2
3 4
2 4
4 1

Sample Output

1 -1

Hint

The adjacency matrix may come in useful for this problem.