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

Обмеження: 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

Примітки

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