Minimum kəsiklər matrisi#5468
Sizə əlaqəli çəkili qraf verilmişdir. Minimum kənar kəsimi, və zirvləri arasında, 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. və zirvləri arasında minimum kəsimin ölçüsünü c_{u,v} kimi qeyd edək.
c_{u,v} matrisini qraf -nin minimum kəsiklər matrisi adlandıracaqıq. Sizə c_{u,v} matrisi verilmişdir. Elə bir qraf tapın ki, c_{u,v} bu qrafın minimum kəsiklər matrisidir və ya belə bir qrafın mövcud olmadığını müəyyən edin.
Giriş faylının ilk sətirində - matrisin ölçüsü (2 \leq n \leq 50) verilir. Növbəti sətir hər biri ə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ə -i keçmir.
Əgər giriş faylındakı matris minimum kəsiklər matrisinə malik bir qraf varsa, çıxış faylının ilk sətirində YES yazın. İkinci sətirdə qrafın kənarlarının sayı -i göstərin. Daha sonra, sətirdə qrafın kənarlarının təsvirlərini verin. Hər bir kənar başlanğıc zirvsi u_i, son zirvsi v_i və u_i və v_i zirvləri arasındakı kənarın çəkisi ilə təyin edilir. Qrafda döngələr, paralel oxlar olmamaldır. Hər bir kənarın çəkisi -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.
Nümunə 1