时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
Rikka and her classmates are playing an online game. There are n players in the game, and there are some pairs of friend relationships among players. The friend relationship is bidirectional.
At the beginning of the game, one player is selected as dragon randomly, and other players are marked as hero.
The game proceeds in turns. Each turn contains the following three steps:
All players want to maximize his/her points, and suppose all players are clever enough.
For each player, Rikka wants you to determine: If this player is selected as the dragon at the beginning, whether the game will end immediately in the first turn?
At the beginning of the game, one player is selected as dragon randomly, and other players are marked as hero.
The game proceeds in turns. Each turn contains the following three steps:
- Each hero is asked to decide whether to attack the dragon. Note that for each player, others' decisions are unknown when making this decision. If a hero is a friend of the dragon, then this hero must choose not to attack;
- If all the heroes choose not to attack the dragon, the game ends immediately. Otherwise, the dragon is eliminated by heroes;
- Suppose player i is the first hero (the player with the smallest index) who chooses to attack. Player i becomes a new dragon and then a new turn starts.
All players want to maximize his/her points, and suppose all players are clever enough.
For each player, Rikka wants you to determine: If this player is selected as the dragon at the beginning, whether the game will end immediately in the first turn?
输入描述:
The first line contains a single integer, representing the number of players.
Then n lines follow. Each line contains an 01-stringof length n.
if and only if player i and player j are friends.
The input guarantees thatand
.
输出描述:
Output a single line with a 01-string res of length n.
if and only if the game will end immediately in the first turn if player i is selected as the first dragon.
示例1
示例2
说明
Without loss of the generality, suppose the third player is selected as the first dragon. Then:
1. For the first player, if he/she chooses to attack, he/she will become the dragon of the second turn. However, according to the first sample, he/she will then be eliminated and will get only 1 point. Therefore, he/she will choose not to attack and thus he/she can get 10 points.
2. For the second player, for the same reason, he/she will choose not to attack, too.
Therefore, the game will end in the first turn.