A new form of bacteria, named Q, is discovered by the famous scientist Dr. Truth. It is known that
Q-bacteria live in a closed environment, called Q-community, without any interaction with other Q-communities. In a community, Q-bacteria stay together in groups. Depending on their DNA structure, a Q-bacterium may or may not be able to transfer a chemical component, called Famma, to another
Q-bacterium. It is also known that Q-bacterium Q1 can transfer Famma to Q-bacterium Q2 if and only
if Q2 can also transfer Famma to Q1 . The chemical component Famma can be synthesized in units of
cells through a complicated process, called Malus, that is invented by Dr. Truth. When a cell of Famma
is first synthesized, it is fresh. A Q-bacterium can process any cell of fresh Famma. A cell of Famma
can be possessed by at most one Q-bacterium at any time. There is no limit on the number of cells of
Famma that a Q-bacterium can possess. After a fresh cell of Famma is possessed by a Q-bacterium, it
is called used. Used Famma can only be transferred to another Q-bacterium. A cell of used Famma in
a Q-bacterium does not (1) disappear, (2) split into parts, (3) combine with other Famma cell, or (4)
drop out of the body of a Q-bacterium unless it is being transferred to another Q-bacterium.
When a Q-bacterium carries a cell of used Famma, it will try to transfer or send away this cell of Famma to another bacterium because this is the way a Q-bacterium to show friendship to fellow Q-bacteria. However, if a cell of used Famma W is currently being carried by a Q-bacterium Q1 and is transferred to another Q-bacterium Q2 , then Q1 does not take back W if it is being transferred from Q2 . However, Q1 can carried W again if it is being transferred from a Q-bacterium that is not Q2 .
Q-bacteria are bad to the health of human and cannot be killed by any known antibiotic. Fortunately, Q-bacteria have built into their DNA structures a property as discovered by Dr. Truth. If a
Famma cell W is being transmitted from Q-bacterium Q1 to Q2 , Q2 will die if Q2 has carried W before
and W has been carried by an odd, but greater than 1, number of different Q-bacteria, including Q2 ,
between now and the previous time Q2 carried it. When a Q-bacterium is dead, every Q-bacterium
in the community will die because the body of a dead Q-bacterium D caused by Famma releases a
chemical component called Verum-i that is lethal to all Q-bacteria within the same community D lives.
Up to today, this is the only known way to kill Q-bacteria.
Given the number Q-bacteria in a community, and their DNA characteristics, you task is find
whether Q-bacteria in this community can be destroyed by exposing to Famma. If it is possible to destroy all Q-bacteria in a
Q-community by dropping Famma, you need to compute the shortest possible time that a Q-bacterium is found dead assuming that it takes one time unit to transfer Famma from one Q-bacterium to another Q-bacterium and it takes no time at all to kill a
Q-bacterium because of the miracle mathematical taste.
The input file contains a set of test data. Each test data consists of two parts representing a Q-community. The first part is the number of Q-bacteria n. Assume that 0 ≤ n ≤ 100, and n = 0 signals the end of the test data.
The second part is a sequence of n lines. The ith line contains the DNA characteristics for the ith bacterium in the form of ai,1 ai,2 ... ai,n where ai,j is 1 if the ith bacterium can transfer Famma
to the jth bacterium; it is 0 if otherwised; Note that there is a single blank between ai,j and ai,j+1 for
each 1 ≤ j < n.
The output file contains exactly n lines. The ith line contains the shortest possible time that a Q-bacterium is found dead after dropping Famma. If the ith input Q-community cannot be destroyed,
please output 0.
3 0 1 1 1 0 1 1 1 0 4 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0
3 0
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Kaohsiung
| No. | Testdata Range | Score |
|---|