Перехрестя у місті з'эднані односторонніми дорогами. Напишіть програму, яка обчислює кількість різних шляхів між кожною парою перехресть. Шляхом називається послідовність односторонніх доріг, які з'єднують перехрестя.

Перехрестя побозначаються невід'ємними цілими числами. Одностороння дорога позначається парою перехресть, які вона з'єднує. Наприклад, 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. Не турбуйтесь про вирівнювання вихідних даних при друку матриць. Всі числа, що виводяться у рядках матриць, повинні відокремлюватись одним пропуском.