[Login|Register]
Problems

Status

Rank

Problem 1412
Obsessive-Compulsive Disorder
Time Limit: 1000ms
Memory Limit: 5000kb
Description
Obsessive–compulsive disorder (OCD) is an anxiety disorder characterized by intrusive thoughts that produce uneasiness, apprehension, fear or worry (obsessions), repetitive behaviors aimed at reducing the associated anxiety (compulsions), or a combination of such obsessions and compulsions. Symptoms of the disorder include excessive washing or cleaning, repeated checking, extreme hoarding, preoccupation with sexual, violent or religious thoughts, relationship-related obsessions, aversion to particular numbers and nervous rituals such as opening and closing a door a certain number of times before entering or leaving a room. These symptoms are time-consuming, might result in loss of relationships with others, and often cause severe emotional and financial distress. The acts of those who have OCD may appear paranoid and potentially psychotic. However, people with OCD generally recognize their obsessions and compulsions as irrational and may become further distressed by this realization. Despite the irrational behaviour, OCD is associated with high verbal IQ.

Unforutunately, Joker Poker has been suffering from this terrible anxiety disorder since very young. There is exactly N places in the USTC and exactly one directed edge between every two places. As a result of OCD, Joker Poker has to choose 3 places A, B and C in the USTC, and walks in cycle like A->B->C->A for 110 times. If he couldn't find such a cycle contains exactly 3 places, he would commit suicide in a very painful and scary way. So you have to tell the principal if Joker Poker could be alive in the USTC.
Input
There are multiple test cases. Each test case starts with a line containing an integer N (1 <= N <= 1000) which is the number of places in the USTC, in the next N lines contain the adjacency matrix A of the relationship(without spaces). Aij = 1 means there is a directed edge from the i-th place to j-th place. Otherwise, Aij = 0. It's guaranteed that Aii = 0, Aij != Aji.
The last line is a 0 indicates the end of the input.
Output
For each case, print “YES” if Joker Poker could be alive in the USTC. Otherwise, please print “NO”.
Sample Input
3
011
001
000
3
010
001
100
0
Sample Output
NO
YES
Hint
Please note that this problem has tight memory limit.
Source
srzmldl
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).