Qraf-turnir#4650
Verilən tapşırıqda sizdən n təpədən ibarət olan bir turnir qrafı qurmaq tələb olunur ki, bu qrafda istənilən iki təpə arasında ən qısa yol iki kənardan çox olmasın.
Döngəsiz istiqamətli qraf turnir adlanır, əgər onun istənilən iki müxtəlif təpəsi arasında yalnız bir kənar varsa (iki mümkün istiqamətdən birində).
Birinci sətirdə qrafın təpələrinin sayı olan yeganə tam ədəd n (3 ≤ n ≤ 1000) verilmişdir.
Əgər təsvir olunan şərtlərə cavab verən heç bir qraf mövcud deyilsə, -1 çıxarın.
Əks halda, tapılmış turnirin qonşuluq matrisini n sətirdə, hər sətirdə boşluqla ayrılmış n ədəd olmaqla çıxarın. Qrafın təpələrinin 1-dən n-ə qədər tam ədədlərlə nömrələndiyini qəbul edin. Onda a_{v,u} = 0, əgər turnirdə v təpəsindən u təpəsinə kənar yoxdursa, və a_{v,u} = 1, əgər kənar varsa.
Çıxarılan qraf turnir olmalıdır, buna görə də aşağıdakı bərabərliklər yerinə yetirilməlidir:
Bütün v, u (1 ≤ v, u ≤ n, v ≠ u) üçün a_{v,u} + a_{u,v} = 1;
Bütün v (1 ≤ v ≤ n) üçün a_{v,v} = 0.
Nümunə 1