Plegma

The trap here is thinking this is a graph connectivity problem. It is not, at least not for the solution. The first run is literally given $C$, the answer. So Player A does not need to prove connectivity to Player B. A only needs to smuggle one bit through the legal choice of one row and one column.

That sounds illegal, but it is exactly the game.

The Anchor

Suppose Player A sends row $r$ and column $c$.

Player B receives:

• the whole row $G_{r,1},G_{r,2},\dots,G_{r,n}$,
• the whole column $G_{1,c},G_{2,c},\dots,G_{n,c}$.

B does not know $r$ or $c$. But B still knows the first value of the received row:

$a = G_{r,1}.$

That is the key fixed anchor. It is not the intersection cell. It is just the value of the chosen row in the first column.

Now define this decoding rule:

• Let $a$ be the first character of the received row.
• If every value in the received column equals $a$, output $a$.
• Otherwise, output $1-a$.

Equivalently, if $D$ means "the received column has some value different from $a$", B outputs

$a \oplus D.$

So Player A only needs to choose a row and column that make this expression equal to the real answer $C$.

Case 1: the first column contains both 0 and 1

Choose $c=1$.

Then the sent column is mixed, so no matter which row A chooses, the column contains a value different from $a=G_{r,1}$. Therefore $D=1$, and B outputs

$a \oplus 1 = 1-a.$

So A picks a row with

$a = 1-C.$

This row exists because the first column contains both values. Then B outputs $C$.

Clean. Slightly cursed, but clean.

Case 2: the first column is all 0

Now every possible chosen row has

$a=0.$

B outputs $0$ if the chosen column is all $0$, and outputs $1$ if the chosen column contains at least one $1$.

• If $C=0$, A chooses $c=1$. The first column is all $0$, so B outputs $0$.
• If $C=1$, A chooses any column containing a $1$. Such a column exists because the grid has at least one $1$. Then B sees a value different from $a=0$ and outputs $1$.

Case 3: the first column is all 1

Now every possible chosen row has

$a=1.$

B outputs $1$ if the chosen column is all $1$, and outputs $0$ if the chosen column contains at least one $0$.

• If $C=1$, A chooses $c=1$. The first column is all $1$, so B outputs $1$.
• If $C=0$, A chooses any column containing a $0$. Such a cell must exist: if the whole grid were all $1$, the grid would definitely be connected. Since $C=0$, the grid is not all $1$. Then B flips and outputs $0$.

Why This Is Enough

Those three cases cover every possible first column:

• mixed,
• all $0$,
• all $1$.

In every case, Player A can choose a valid row and column that force B's fixed decoding rule to return exactly $C$.

Notice how little actual connectivity we used. The only connectivity-related fact we need is this tiny one:

If every cell is $1$, then the grid is connected.

So when $C=0$, there must be at least one $0$ somewhere.

Everything else is just communication protocol nonsense. Very Codeforces. Very evil. Very funny after it stops hurting.

Complexity

On the first run, we scan the grid to inspect the first column and find any needed opposite bit, so the total work is $O(n^2)$ per test case.

On the second run, we scan one received column, so it is $O(n)$.

The total input size is bounded by $\sum n^2 \le 2\cdot 10^6$, so this is easily fast enough.