Minimum kəsiklər matrisi
Sizə əlaqəli çəkili qraf G verilmişdir. Minimum kənar kəsimi, u və v zirvələri arasında, u və v arasında hər hansı bir yolun C_{u,v} kənarlarından ən azı birini ehtiva etdiyi, ən kiçik cəmi çəkiyə malik C_{u,v} kənarları çoxluğudur. u və v zirvələri arasında minimum kəsimin ölçüsünü c_{u,v} kimi qeyd edək.
c_{u,v} matrisini qraf G-nin minimum kəsimlər matrisı adlandıracağıq. Sizə c_{u,v} matrisi verilmişdir. Elə bir qraf G tapın ki, c_{u,v} bu qrafın minimum kəsimlər matrisidir və ya belə bir qrafın mövcud olmadığını müəyyən edin.
Giriş verilənləri
Giriş faylının ilk sətirində n - matrisin ölçüsü (2 ≤ n ≤ 50) verilir. Növbəti n sətir hər biri n ədəd olmaqla matrisin elementlərini ehtiva edir. Matrisin simmetrik olduğu və əsas diaqonalda yalnız sıfırların olduğu təmin edilir. Digər bütün ədədlər müsbətdir və 1000-i keçmir.
Çıxış verilənləri
Əgər giriş faylındakı matris minimum kəsimlər matrisinə malik bir qraf G varsa, çıxış faylının ilk sətirində YES yazın. İkinci sətirdə qrafın kənarlarının sayı M-i göstərin. Daha sonra, m sətirdə qrafın kənarlarının təsvirlərini verin. Hər bir kənar i başlanğıc zirvəsi u_i, son zirvəsi v_i və u_i və v_i zirvələri arasındakı kənarın çəkisi ilə təyin edilir. Qrafda döngələr, paralel oxlar olmamalıdır. Hər bir kənarın çəkisi 1000-i keçməməlidir.
Əgər şərti təmin edən qraf mövcud deyilsə, çıxış faylının yeganə sətirində NO yazın.