Altars and Gems

The altar is in the shape of a regular $n$-gon. At each vertex there is an inactive gem, and the gems are numbered from $1$ to $n$. Between every pair of distinct gems $(i,j)$, there is a one‐way energy flow: either from $i$ to $j$ or from $j$ to $i$. This yields a tournament graph on $n$ nodes.

In order to activate the altar, all gems must be activated. The process is as follows: first, one gem is chosen and activated initially. Then a number of energy transmissions occur. In each transmission, any gem $y$ that is not yet activated will become activated if there exists an already activated gem $x$ such that there is energy flowing from $x$ to $y$ (i.e. an edge $x\to y$). Once activated, a gem remains activated.

Altair wants to choose a gem to initially activate such that the total number of energy transmissions required to eventually activate all gems is minimized. To help decide, Altair is allowed to perform several energy sensing operations. In one energy sensing operation, given two distinct gems $i$ and $j$ ($1 \le i,j \le n$), the sensing operation sense(i,j) will reveal whether the energy flows from $i$ to $j$ (returns true) or from $j$ to $i$ (returns false). You are guaranteed that the total number of sense operations in one call is at most $4.5 \times 10^4$.

It can be proven that there is always at least one gem which, if chosen for initial activation, will eventually activate all gems in finitely many energy transmissions, and moreover it will achieve the minimum number of transmissions possible. Your task is to implement the function:

int altar(int n);

Here, n is the number of gems on the altar. The function should return an integer between $1$ and $n$, indicating the gem which, when initially activated, minimizes the number of energy transmissions required to activate all gems.

Note: In the final test, the interactive grader will call the function altar $T=300$ times with a fixed energy flow configuration. Your solution should not assume that the energy flow relations change during these calls.

The following function is available for you to perform an energy sensing operation:

bool sense(int i, int j); // Returns true if energy flows from i to j, false otherwise.

inputFormat

The input begins with an integer T specifying the number of test cases. Each test case is described as follows:

• An integer n ($1 \le n \le$ some limit) representing the number of gems.
• An n × n matrix where the j-th number in the i-th row is either 0 or 1. For any two distinct indices i and j, exactly one of the two values M[i][j] and M[j][i] is 1. We guarantee that M[i][i] = 0 for all i.

This matrix represents the energy flow: if the number at position (i,j) is 1, then energy flows from gem i to gem j (i.e. sense(i,j) returns true).

Note: While the intended problem is interactive, in the test cases you will be provided the full matrix.

outputFormat

For each test case, output a single integer on a new line. This integer (between 1 and n) is the gem that should be initially activated to achieve the minimum number of energy transmissions required to eventually activate all gems.

sample

3
0 1 0
0 0 1
1 0 0

3