Almost Rainbow Permutation (Hard Version) - Weekly Challenge 1: Approximation | Repovive

W1D4B. Almost Rainbow Permutation (Hard Version)

2 pts3s256 MB

You are given an $n \times n$ matrix $a$ . Every element of the matrix is an integer between $1$ and $n$ .

It is guaranteed that there exists a permutation $p_1, p_2, \ldots, p_n$ such that the values

$a_{1,p_1}, a_{2,p_2}, \ldots, a_{n,p_n}$

are pairwise distinct.

Choose at least $\left\lceil \frac{n}{2} \right\rceil$ cells of the matrix such that:

no two chosen cells are in the same row;
no two chosen cells are in the same column;
no two chosen cells contain the same value.

It can be proven that such a choice always exists.

Constraints

$1 \le n \le 600$
$1 \le a_{i,j} \le n$
There exists a permutation $p_1, p_2, \ldots, p_n$ such that $a_{1,p_1}, a_{2,p_2}, \ldots, a_{n,p_n}$ are pairwise distinct

Input

n

\begin{array}{cccc} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \end{array}

Output

First, output an integer $k$ , the number of chosen cells.

Then output $k$ pairs. The $i$ -th pair $r_i, c_i$ denotes that the cell in row $r_i$ and column $c_i$ is chosen.

If there are several valid answers, output any of them.

\begin{array}{l} k \\ r_1 \quad c_1 \\ r_2 \quad c_2 \\ \vdots \\ r_k \quad c_k \end{array}

Samples

Input

Explanation

The cells $(1,1)$ , $(2,2)$ , and $(3,3)$ contain the distinct values $1$ , $3$ , and $5$ . They also use different rows and different columns, so the output is valid.

Output

You are given an $n \times n$ matrix $a$ . Every element of the matrix is an integer between $1$ and $n$ .

It is guaranteed that there exists a permutation $p_1, p_2, \ldots, p_n$ such that the values

$a_{1,p_1}, a_{2,p_2}, \ldots, a_{n,p_n}$

are pairwise distinct.

Choose at least $\left\lceil \frac{n}{2} \right\rceil$ cells of the matrix such that:

no two chosen cells are in the same row;
no two chosen cells are in the same column;
no two chosen cells contain the same value.

It can be proven that such a choice always exists.

$1 \le n \le 600$
$1 \le a_{i,j} \le n$
There exists a permutation $p_1, p_2, \ldots, p_n$ such that $a_{1,p_1}, a_{2,p_2}, \ldots, a_{n,p_n}$ are pairwise distinct

n

\begin{array}{cccc} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \end{array}

First, output an integer $k$ , the number of chosen cells.

Then output $k$ pairs. The $i$ -th pair $r_i, c_i$ denotes that the cell in row $r_i$ and column $c_i$ is chosen.

If there are several valid answers, output any of them.

\begin{array}{l} k \\ r_1 \quad c_1 \\ r_2 \quad c_2 \\ \vdots \\ r_k \quad c_k \end{array}

The cells $(1,1)$ , $(2,2)$ , and $(3,3)$ contain the distinct values $1$ , $3$ , and $5$ . They also use different rows and different columns, so the output is valid.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

W1D4B. Almost Rainbow Permutation (Hard Version)

Constraints

Input

Output

Samples

W1D4B. Almost Rainbow Permutation (Hard Version)

Constraints

Input

Output

Samples