Remote Training on Programming

Задан ориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая подсчитывает количество различных путей между всеми парами вершин графа.

Input

Количество вершин графа N (1<=N<=33) и список дуг графа, заданных номерами начальной и конечной вершин.

Output

Вывести матрицу NxN, элемент (i,j) которой равен числу различных путей, ведущих из вершины i в вершину j, или -1, если существует бесконечно много таких путей.

Sample

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

-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 0 -1 0
-1 -1 1 -1 0