Зоряні шляхи
Космічні мандрівники знайшли інформацію про шляхи між зоряними воротами. Використовуючи їх можно попасти в інші світи через космічні гіпертунелі. Шляхи між зорями, які існують у різних світах, задано матрицею. Всі ворота мають номери (1 ≤ i ≤ 100). Матриця шляхів містить 1 (одиницю) в позиції (i,j), якщо існує прямий шлях від зірки (i) до зірки (j).
Всі інші позиції містять 0 (нуль). Існування прямого шляху від зірки (i) до зірки (j) не гарантує існування такого ж шляху від (j) до (i). Але завжди є 1 в позиціях (i,i).
Задача полягає в настпуному. За заданою матрицею шляхів ви повинні знайти матрицю продвинутих шляхів, яка показує всі можливі шляхи. Ця матриця повинна давати інформацію про досягненість зірки (k) від кожної іншої зірки (i). Тобто, якщо існують шляхи від зірки (i) до зірки (j) і від зірки (j) до зірки (k), то існує також шлях і від (i) до (k). Існування шляху також представляеться числом 1 у відповідній позиції матриці.
Так що продвинутий шлях може бути не обовязково прямим, але і містити проміжні зоряні ворота.
Вхідні дані
У першому рядку задано розмір матриці M (M ≤ 100), наступні рядки - рядки матриці. Елементи в рядках відокремлюються одним пропуском. Вхідні дані коректні.
Вихідні дані
Виведення - це матриця продвинутих шляхів, записана по рядках, елементи відокремлюються одним пропуском.