F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Difference

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1053    Accepted Submission(s): 317

Problem Description
A graph is a difference if every vertex vi can be assigned a real number ai and there exists a positive real number T such that
(a) |ai| < T for all i and
(b) (vi, vj) in E <=> |ai - aj| >= T,
where E is the set of the edges.
Now given a graph, please recognize it whether it is a difference.

Input
The first line of input contains one integer TC(1<=TC<=25), the number of test cases.
Then TC test cases follow. For each test case, the first line contains one integer N(1<=N<=300), the number of vertexes in the graph. Then N lines follow, each of the N line contains a string of length N. The j-th character in the i-th line is "1" if (vi, vj) in E, and it is "0" otherwise. The i-th character in the i-th line will be always "0". It is guaranteed that the j-th character in the i-th line will be the same as the i-th character in the j-th line.

Output
For each test case, output a string in one line. Output "Yes" if the graph is a difference, and "No" if it is not a difference.

Sample Input
3
4
0011
0001
1000
1100
4
0111
1001
1001
1110
3
000
000
000


Sample Output
Yes
No
Yes

Hint

In sample 1, it can let T=3 and a1=-2, a2=-1, a3=1, a4=2.

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.001000(s) query 1, Server time : 2024-08-14 18:51:00, Gzip enabled Administration