![]()
1 #include <bits/stdc++.h>
2 #define dbg(x) cout << #x << "=" << x << endl
3 #define eps 1e-8
4 #define pi acos(-1.0)
5
6 using namespace std;
7 typedef long long LL;
8
9 template<class T>inline void read(T &res)
10 {
11 char c;T flag=1;
12 while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
13 while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
14 }
15
16 namespace _buff {
17 const size_t BUFF = 1 << 19;
18 char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
19 char getc() {
20 if (ib == ie) {
21 ib = ibuf;
22 ie = ibuf + fread(ibuf, 1, BUFF, stdin);
23 }
24 return ib == ie ? -1 : *ib++;
25 }
26 }
27
28 int qread() {
29 using namespace _buff;
30 int ret = 0;
31 bool pos = true;
32 char c = getc();
33 for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
34 assert(~c);
35 }
36 if (c == '-') {
37 pos = false;
38 c = getc();
39 }
40 for (; c >= '0' && c <= '9'; c = getc()) {
41 ret = (ret << 3) + (ret << 1) + (c ^ 48);
42 }
43 return pos ? ret : -ret;
44 }
45
46 const int maxn = 507;
47
48 struct node
49 {
50 int u,v,w;
51 }e[maxn*maxn];
52
53 int fa[maxn];
54 LL g[maxn][maxn];
55 LL dis[maxn][maxn];
56
57 int tot[maxn];
58
59 int fid(int x)
60 {
61 return fa[x]==x ? x : fa[x] = fid(fa[x]);
62 }
63
64 bool cmp(node a,node b)
65 {
66 return a.w < b.w;
67 }
68
69 int main()
70 {
71 int n;
72 int num=0,x,sum=0;
73 read(n);
74 for(int i = 1; i <= n; ++i) {
75 for(int j = 1; j <= n; ++j) {
76 read(x);
77 g[i][j] = x;
78 if(i != j)
79 {
80 e[++num].w=x;
81 e[num].u=i;
82 e[num].v=j;
83 }
84 }
85 }
86 sort(e+1,e+num+1,cmp);
87 for(int i = 1; i <= n; ++i) {
88 for(int j = 1; j <= n; ++j) {
89 if(i == j) dis[i][j] = 0;
90 else dis[i][j] = 1e18;
91 }
92 }
93 for(int i = 1; i <= n; ++i) {
94 fa[i] = i;
95 }
96 int u,v;
97 for(int i = 1;i <= num; ++i) {
98 u = e[i].u;
99 v = e[i].v;
100 if(fid(u)!=fid(v))
101 {
102 dis[u][v] = dis[v][u] = e[i].w;
103 tot[++sum] = e[i].w;
104 fa[fa[u]] = fa[v];
105 }
106 }
107 for(int k = 1; k <= n; ++k) {
108 for(int i = 1; i <= n; ++i) {
109 for(int j = 1; j <= n; ++j) {
110 dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
111 }
112 }
113 }
114 for(int i = 1; i <= n; ++i) {
115 for(int j = 1; j <= n; ++j) {
116 if(dis[i][j] != g[i][j]) {
117 printf("No");
118 return 0;
119 }
120 }
121 }
122 printf("Yes
");
123 sort(tot+1,tot+n);
124 for(int i = 1; i < n; ++i) {
125 printf("%d
",tot[i]);
126 }
127 }
