ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. The Party of Ural Champions

Time limit: 1.0 second
Memory limit: 64 MB
Because of the coming election to the Regional Duma, all the billboards along the roads in Yekaterinburg have been replaced. They are now agitating for the Party of Ural Champions. There are n intersections in Yekaterinburg, and some of them are connected by two-way roads. Any two intersections are connected by a sequence of such roads. There can be at most one billboard on any road connecting two intersections. Each billboard faces one side only, which means that the agitation can be seen by drivers moving in only one of the two directions.
The Party of Ural Champions has presented a report to the election committee, in which it has given information on the campaign materials. In particular, for each pair of intersections the report specifies the minimum number of times a car driver will see the agitation when driving from the first of these intersection to the second regardless of the route he would take.
Chairman of the Regional Election Committee suspects that there is an error in the report, because there is no configuration of roads and no arrangement of billboards corresponding to the given data. Your task is to verify this assertion.

Input

The first line contains the integer n (2 ≤ n ≤ 300). In each of the following n lines you are given n integers separated with a space. The number in the i-th line at the j-th position is equal to the minimum number of times a car driver will see the agitation when driving from the i-th intersection to the j-th intersection. All the integers in this table are in the range from 0 to n − 1. All the numbers on the main diagonal are zeros.

Output

If there is a configuration of roads and billboards that corresponds to the data in the report, then output “YES” in the first line. Then output n lines containing n symbols each. In the i-th line at the j-th position output
  • “0” if the i-th and the j-th intersections are not connected by a road;
  • “1” if the i-th and the j-th intersections are connected by a road but there is no billboard on this road or there is a billboard but a car driver will not see the agitation when driving from the i-th intersection to the j-th intersection;
  • “2” if the i-th and the j-th intersections are connected by a road and a car driver will see the agitation when driving from the i-th intersection to the j-th intersection.
No intersection can be connected by a road with itself. If several answers are possible, output any of them.
If there is no required configuration of roads and billboards, output “NO” in the only line.

Samples

inputoutput
5
0 1 1 1 1
1 0 1 0 1
0 0 0 0 0
2 1 2 0 2
0 0 0 0 0
YES
00202
00210
11001
02000
10100
2
0 1
1 0
NO
Problem Author: Igor Chevdar
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010
To submit the solution for this problem go to the Problem set: 1770. The Party of Ural Champions