Intersection of Maximum Happiness Perfect Matchings

There are \(N\) single boys and \(N\) single girls. For each boy \(i\) and girl \(j\), the happiness value of their pairing is given by \(H_{i,j}\). A matching is an assignment that pairs every boy with exactly one girl and every girl with exactly one boy. The total happiness of a matching is the sum of happiness values of the paired couples.

The classic problem is to find a perfect matching with the maximum total happiness. However, the maximum perfect matching may not be unique. In this problem, you are asked to compute the intersection of all maximum perfect matchings; that is, find all pairs \((i,j)\) that appear in every perfect matching achieving the maximum total happiness.

Note: In both input and output, indices are 1-indexed.

inputFormat

The first line contains an integer \(N\) denoting the number of boys (and girls). The next \(N\) lines each contain \(N\) integers. The \(j\)-th integer in the \(i\)-th line represents the happiness value \(H_{i,j}\) when boy \(i\) and girl \(j\) form a pair.

outputFormat

On the first line, output an integer \(K\) which is the number of pairs that appear in every maximum perfect matching. Then output \(K\) lines, each containing two integers \(i\) and \(j\) indicating that boy \(i\) and girl \(j\) are paired in every maximum perfect matching. The pairs should be output in increasing order of boy index.

sample

3
1 2 3
3 2 1
2 3 2

3
1 3
2 1
3 2