CMPANS - Comparing Answers

In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were n cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.



Input

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer n (1 ≤ n ≤ 700). The following n lines contain n elements each, with element j of line i being the number of roads from city i to city j (a number between 0 and 10, inclusive). After that, there will be n lines. Each will contain n elements, with element j of line i being the answer from your friend for the number of length-2 paths from city i to city j; it will be an integer between 0 and 100 000 inclusive.

The test cases will finish with a line containing only the number zero (also preceded by a blank line).

Note: Large input file; use fast I/O routines (e.g. scanf in C++ or BufferedReader in Java).



Output

For each case, your program should output a line. The content of this line should be YES if your classmate’s solution to the assignment is right, and NO otherwise.



Sample Input

3
2 0 1
1 0 3
1 1 0
5 1 2
5 3 1
3 0 4

3
2 0 1
1 0 3
1 1 0
5 1 2
5 3 2
3 0 4

0



Sample Output

YES
NO

Problemsetter: Abel Molina Prieto

Added by:David GarcĂ­a Soriano
Date:2011-11-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Southwestern Europe Regional, SWERC 2010

hide comments
2017-04-19 23:12:39
strassens matrix multipliction!!
2013-09-04 02:47:17 田寅
please help 105557212@qq.com
2011-12-12 04:14:07 [Rampage] Blue.Mary
You needn't calculate the result of the square of the first Matrix.
2011-12-11 23:58:16 Himanshu
matrix multiplication problem ....but how to do it in less than O(n^3)....any help...

Last edit: 2011-12-11 23:59:15
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.