Розміщення доріг

Обмеження: 2 сек., 256 МіБ

Знаєте, Зеник та Марічка активно дбають про суспільне життя своєї країни. От сьогодні вони отримали унікальне право побудувати нормальні дороги між містами (вигравши тендер, звісно).

Усього є \(n\) міст. Спочатку між ними немає жодної дороги. Кожна побудована дорога повинна вести з деякого міста \(v\) в деяке місто \(u\) та мати певну цілу додатну довжину \(c\). Зауважте, що Марічка з Зеником самі можуть вибирати ці значення. Марічка вважає дорожню систему хорошою, якщо виконуються такі умови:

• Немає жодної дороги, яка веде з міста в самого себе.

• Довжина кожної дороги є цілою та додатною.

• З деякого міста \(v\) в деяке місто \(u\) може вести не більше однієї дороги.

• Найкоротший шлях з вершини 1 до вершини \(i\) рівний \(d_i\).

• Кількість різних найкоротших шляхів з вершини 1 до вершини \(i\) рівна \(c_i\).

Допоможіть нашим героям знайти потрібне розміщення доріг або скажіть, що немає жодного хорошого варіанту. Якщо ж варіантів декілька, виведіть будь-який.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість міст.

У наступних \(n-1\) рядках задано по два цілих числа \(d_i\), \(c_i\) для міст з номерами від 2 до \(n\).

Вихідні дані

У першому рядку виведіть YES, якщо можливо побувати дороги, і NO навпаки.

Якщо існує хороша дорожня система, виведіть також \(n\) рядків по \(n\) чисел у кожному — \(j\)-те число в \(i\)-ому рядку рівне довжині дороги з міста \(i\) в місто \(j\), якщо така дорога існує, і -1 навпаки.

Обмеження

\(1 \le n \le 500\),

\(1 \le d_i, c_i \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 47 2 4 1 7 1	YES -1 -1 4 7 -1 -1 -1 -1 -1 43 -1 -1 -1 40 -1 -1

Примітки

Дана система доріг задовольняє всі необхідні умови. Зауважте, що існують і інші хороші варіанти.