Перекрестки в городе соединены односторонними дорогами. Напишите программу, которая вычисляет количество разных путей между каждой парой перекрестков. Путем называется последовательность односторонних дорог, соединяющих перекрестки.

Перекрестки обозначаются неотрицательными целыми числами. Односторонняя дорога обозначается парой перекрестков, которые она соединяет. Например, j k указывает на то, что односторонняя дорога идет от перекрестка j к перекрестку k. Заметим, что двусторонняя дорога может быть промоделирована двумя односторонними: j k и k j.

Рассмотрим город с четырьмя перекрестками, которые соединены улицами следующим образом:

0 1

0 2

1 2

2 3

Существует только один путь между перекрестками 0 и 1, два пути между 0 и 2 (это 0 → 1 → 2 и 0 → 2), два пути между 0 и 3, один путь между 1 и 2, один путь между 1 и 3, один путь между 2 и 3, других путей не существует.

Возможно, между некоторыми перекрестками существует бесконечное количество путей. Например, если к описанному выше множеству дорог добавить 3 2, между 0 и 1 останется один путь, но появится бесконечное количество путей между 0 и 2. Потому что из 2 в 3 и назад из 3 в 2 можно двигаться произвольное количество раз, получая бесконечное количество разных путей. То есть пути 0 → 2 → 3 → 2 → 3 → 2 и 0 → 2 → 3 → 2 разные.

Входные данные

Первое число содержит количество односторонних улиц в городе, за которым следует их описание. Каждая улица задается парой перекрестков, которые она соединяет: каждая пара j k представляет собой одностороннюю улицу от перекрестка j к перекрестку k. Во всех городах перекрестки последовательно пронумерованы с 0 до "наибольшего" перекрестка. Все входные целые числа разделены одним пробелом.

Ни одна из односторонних улиц не ведет от перекрестка к нему же самому. Ни один из городов не имеет больше 30 перекрестков.

Выходные данные

Вывести квадратную матрицу, содержащую информацию о количестве разных путей между перекрестками j и k. Если обозначить выводимую матрицу через M, то M[j][k] - это количество разных путей, ведущих от перекрестка j к перекрестку k. Матрицу M выводить построчно, в порядке возрастания строк.

Если между двумя перекрестками существует бесконечное количество путей, вывести -1. Не беспокойтесь о выравнивании выходных данных при печати матриц. Все выводимые числа в строках матриц должны разделяться одним пробелом.