Critical Edge in Complete Graph

Given an undirected complete graph with n vertices and positive weights, determine for each edge (a, b) whether there exists a pair of vertices (x, y) such that all shortest paths from x to y pass through the edge (a, b).

In this problem, consider the pair (a, b) itself. An edge (a, b) is said to be critical if the following condition holds for every vertex c different from a and b:

If the inequality fails for any such vertex (including the case of equality), then there exists an alternative shortest path from a to b that does not use the edge (a,b), and the edge is not critical.

Note: Since the graph is complete, every pair of distinct vertices has a direct edge. Therefore, checking the pair (a, b) itself is sufficient.

inputFormat

The first line contains a single integer n representing the number of vertices. The next n lines each contain n space-separated integers forming the weight matrix of the graph. The element in the i-th row and j-th column represents the weight of the edge between vertex i and vertex j. It is guaranteed that the diagonal elements are 0 and for i ≠ j, the weights are positive.

outputFormat

For each edge (a, b) with 1 ≤ a < b ≤ n, output a single line containing YES if the edge is critical (i.e. if for every vertex c with c ≠ a and c ≠ b the inequality $$w(a,b) < w(a,c) + w(c,b)$$ holds). Otherwise, output NO.

sample

3
0 1 3
1 0 4
3 4 0

YES
YES
NO