CF2163E.Plegma

This is a run-twice (communication) problem.

There are two players: Player A and Player B. The jury will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information or receive information from the jury, but they may agree on the strategy they will use to communicate.

The jury has a binary grid $G$ of $n$ rows and $n$ columns (each cell of this grid has value either $0$ or $1$). Row $1$ is the top-most row, and column $1$ is the left-most column. The connectivity of this grid is defined as $1$ if there is a path going left, right, up, or down going through only cells with value $1$ connecting each pair of cells $(i_1,j_1)$ and $(i_2,j_2)$ with $G_{i_1,j_1}=G_{i_2,j_2}=1$. Note that moving diagonally is not allowed. It is guaranteed that there exists at least one cell with value of $1$ in this grid.

The jury first interacts with player A. The jury will give player A the grid $G$. After inspecting the grid, player A must determine two integers $r$ and $c$ and send them to the jury. At the start of player B's interaction, player B will receive the values of all cells in the $r$'th row and all cells in the $c$'th column from the jury. Note that player B is not given the values of $r$ and $c$.

Player A wants to ensure player B can determine the connectivity of $G$. Your task is to act as both players and find a strategy so that player B is able to determine the connectivity correctly. Note that the communicator of this task is not adaptive – that is, the grid given to you on the first run will be the same as the grid used to evaluate the connectivity.

这是一个需运行两次（通信）的问题。

共有两名玩家：玩家 A 和玩家 B。裁判首先与玩家 A 交互；在玩家 A 结束交互后，裁判再与玩家 B 交互。注意，玩家 A 与玩家 B 之间不能直接传递信息；双方都只能向裁判发送信息或从裁判处接收信息，但他们可以事先约定将采用的通信策略。

裁判持有一个大小为 $n \times n$ 的二进制网格 $G$（该网格每个单元格的值为 $0$ 或 $1$）。第 $1$ 行为最上方的行，第 $1$ 列为最左方的列。该网格的连通性定义如下：若对任意两个满足 $G_{i_1,j_1}=G_{i_2,j_2}=1$ 的单元格 $(i_1,j_1)$ 与 $(i_2,j_2)$，均存在一条仅经过值为 $1$ 的单元格、且每一步仅允许向上、下、左、右移动（不允许对角线移动）的路径将其连接，则连通性为 $1$。题目保证该网格中至少存在一个值为 $1$ 的单元格。

裁判首先与玩家 A 交互：裁判将网格 $G$ 提供给玩家 A。玩家 A 在观察完该网格后，必须确定两个整数 $r$ 和 $c$，并将它们发送给裁判。在玩家 B 的交互开始时，裁判会将网格 $G$ 中第 $r$ 行的所有单元格值以及第 $c$ 列的所有单元格值提供给玩家 B。注意：玩家 B 不会被告知 $r$ 和 $c$ 的具体取值。

玩家 A 的目标是确保玩家 B 能够正确判定网格 $G$ 的连通性。你的任务是同时扮演两名玩家，设计一种策略，使得玩家 B 总能正确判定连通性。注意：本题的通信器是非自适应的——即第一次运行时所给定的网格，与用于最终判定连通性的网格完全相同。

Your code will be ran exactly two times on each test. On the first run, you will be Player A, and on the second Player B.

First Run Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Player A.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $C$ ($2 \leq n \leq 1000, 0 \leq C \leq 1$) – the size of the grid and the connectivity respectively.

The following $n$ lines contain information about the grid. The $i$th of these lines contains a binary string $G_i$ of length $n$, indicating the $i$-th row of the grid.

It is guaranteed that:

• The sum of $n^2$ does not exceed $2\cdot 10^6$ over all test cases
• The value of $C$ matches with the information in the grid – that is, if $C=1$, then the grid has connectivity $1$, and if $C=0$, then the grid has connectivity $0$.
• Each grid has at least one $1$ in the input.

Second Run Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Player B.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. Note that this number is equal to $t$ from the first run input.

The first line of each test case contains exactly one integer $n$ — the size of the grid given on the $i$'th test case of the first run input.

The second line of each test case contains a binary string $G_{r, 1}G_{r, 2}\ldots G_{r, n}$ — the contents in row $r$ of the grid. Note that the integer $r$ is sent by player A to the jury at the end of their interaction of the $i$'th test case

The third line of each test case contains a binary string $G_{1, c}G_{2, c}\ldots G_{n, c}$ — the contents in column $c$ of the grid. Note that the integer $c$ is sent by player A to the jury at the end of their interaction of the $i$'th test case.

Hacks

To make hacks, use the following format:

The first line should contain exactly one integer $t$ $(1 \le t \le 10^4)$ — the number of grids. Then, $t$ blocks of input should follow.

The first line of each block of input must contain a single integer $n$ $(2 \le n \le 1000)$ — the size of the grid the jury will choose.

Each of the next $n$ lines should contain a binary string of size $n$. The $i$'th of these lines should contain $G_{i, 1}G_{i, 2}\ldots G_{i, n}$ — the contents of the $i$'th row of the grid the jury will choose.

There must exist at least a single cell with value of $1$ in each grid, and the sum of $n^2$ over all test cases should not exceed $2\cdot 10^6$.

Note that the connectivity of each grid is determined by the jury, and you do not need to output it for a hack.

你的代码将在每个测试用例上恰好运行两次：第一次运行时，你作为玩家 A；第二次运行时，你作为玩家 B。

第一次运行的输入

输入的第一行包含字符串 first。其作用是让你的程序识别出这是第一次运行，因此应以玩家 A 的身份行动。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $C$（$2 \leq n \leq 1000,\ 0 \leq C \leq 1$）——分别表示网格大小和连通性参数。

接下来的 $n$ 行描述该网格。其中第 $i$ 行是一个长度为 $n$ 的二进制字符串 $G_i$，表示网格的第 $i$ 行。

保证以下条件成立：

• 所有测试用例中 $n^2$ 的总和不超过 $2\cdot 10^6$；
• $C$ 的取值与网格实际连通性一致：若 $C=1$，则该网格连通性为 $1$；若 $C=0$，则连通性为 $0$；
• 每个网格输入中至少包含一个 1。

第二次运行的输入

输入的第一行包含字符串 second。其作用是让你的程序识别出这是第二次运行，因此应以玩家 B 的身份行动。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。注意：该数值与第一次运行输入中的 $t$ 相同。

每个测试用例的第一行仅包含一个整数 $n$ —— 即第一次运行中第 $i$ 个测试用例所给定的网格大小。

每个测试用例的第二行是一个二进制字符串 $G_{r, 1}G_{r, 2}\ldots G_{r, n}$ —— 表示该网格第 $r$ 行的内容。注意：整数 $r$ 是玩家 A 在第 $i$ 个测试用例交互结束时发送给裁判的。

每个测试用例的第三行是一个二进制字符串 $G_{1, c}G_{2, c}\ldots G_{n, c}$ —— 表示该网格第 $c$ 列的内容。注意：整数 $c$ 是玩家 A 在第 $i$ 个测试用例交互结束时发送给裁判的。

Hack 输入格式

要进行 hack，请使用如下格式：

第一行应恰好包含一个整数 $t$（$1 \le t \le 10^4$）——表示网格数量。随后需跟 $t$ 个输入块。

每个输入块的第一行必须是一个整数 $n$（$2 \le n \le 1000$）——表示裁判将选取的网格大小。

接下来的 $n$ 行每行应是一个长度为 $n$ 的二进制字符串。其中第 $i$ 行应为 $G_{i, 1}G_{i, 2}\ldots G_{i, n}$ —— 表示裁判将选取的网格中第 $i$ 行的内容。

每个网格中必须至少存在一个值为 1 的格子，且所有测试用例中 $n^2$ 的总和不得超过 $2\cdot 10^6$。

注意：每个网格的连通性由裁判确定，你在 hack 中无需输出该连通性值。

For the first run, for each test case, output two integers $r$ and $c$ ($1 \leq r,c \leq n$). This indicates that you want the second run to receive the $r$-th row and the $c$-th column of the grid.

For the second run, for each test case, output an integer $C$ ($0 \leq C \leq 1$) – the connectivity of the grid.

首次运行时，对每个测试用例，输出两个整数 $r$ 和 $c$（$1 \leq r,c \leq n$）。这表示你希望第二次运行接收该网格的第 $r$ 行和第 $c$ 列。

第二次运行时，对每个测试用例，输出一个整数 $C$（$0 \leq C \leq 1$）——即该网格的连通性。

On the first input example, the first grid is the following:

1

1

1

0

On the first run, we know that $n = 2$. After inspecting the example, we can determine that the connectivity is $1$.

For the sake of this example, suppose Player A and Player B have agreed to some strategy where if the connectivity is $1$, then player A should send a row and a column that both end with $0$. In this case, row $2$ and column $2$ satisfies this strategy. Note that this is an example strategy for the sake of demonstration, and using this strategy will not work for all cases.

Then, take a look at the second run. Now, we are Player B. We receive that $n = 2$ and that the chosen row has values $r = [1, 0]$ and the chosen column has values $c = [1, 0]$. Since the last number of each row is $0$, player B uses the agreed upon strategy to determine that the connectivity is $1$.

在第一个输入样例中，第一个网格如下所示：

1

1

1

0

在第一次运行中，已知 $n = 2$。通过观察该样例，我们可以确定连通性（connectivity）为 $1$。

为便于说明本例，假设玩家 A 和玩家 B 已约定某种策略：若连通性为 $1$，则玩家 A 应发送一个以 $0$ 结尾的行和一个以 $0$ 结尾的列。此时，第 $2$ 行与第 $2$ 列满足该策略。请注意，这只是为演示而构造的示例策略，该策略并不能适用于所有情况。

接着，观察第二次运行。此时，我们扮演玩家 B。我们收到 $n = 2$，且所选行的值为 $r = [1, 0]$，所选列的值为 $c = [1, 0]$。由于该行与该列的最后一个数均为 $0$，玩家 B 根据双方约定的策略判定连通性为 $1$。