# [Solution] Serega the Pirate solution codeforces

Serega the Pirate solution codeforces – Little pirate Serega robbed a ship with puzzles of different kinds. Among all kinds, he liked only one, the hardest.

Table of Contents

## [Solution] Serega the Pirate solution codeforces

A puzzle is a table of 𝑛n rows and 𝑚m columns, whose cells contain each number from 11 to 𝑛𝑚n⋅m exactly once.

To solve a puzzle, you have to find a sequence of cells in the table, such that any two consecutive cells are adjacent by the side in the table. The sequence can have arbitrary length and should visit each cell one or more times. For a cell containing the number 𝑖i, denote the position of the first occurrence of this cell in the sequence as 𝑡𝑖ti. The sequence solves the puzzle, if 𝑡1<𝑡2<<𝑡𝑛𝑚t1<t2<⋯<tnm. In other words, the cell with number 𝑥x should be first visited before the cell with number 𝑥+1x+1 for each 𝑥x.

Let’s call a puzzle solvable, if there exists at least one suitable sequence.

In one move Serega can choose two arbitrary cells in the table (not necessarily adjacent by the side) and swap their numbers. He would like to know the minimum number of moves to make his puzzle solvable, but he is too impatient. Thus, please tell if the minimum number of moves is 0011, or at least 22. In the case, where 11 move is required, please also find the number of suitable cell pairs to swap.

## [Solution] Serega the Pirate solution codeforces

In the first line there are two whole positive numbers 𝑛,𝑚n,m (1𝑛𝑚4000001≤n⋅m≤400000) — table dimensions.

In the next 𝑛n lines there are 𝑚m integer numbers 𝑎𝑖1,𝑎𝑖2,,𝑎𝑖𝑚ai1,ai2,…,aim (1𝑎𝑖𝑗𝑛𝑚1≤aij≤nm).

It is guaranteed that every number from 11 to 𝑛𝑚nm occurs exactly once in the table.

Output

Let 𝑎a be the minimum number of moves to make the puzzle solvable.

If 𝑎=0a=0, print 00.

If 𝑎=1a=1, print 11 and the number of valid swaps.

If 𝑎2a≥2, print 22.

## [Solution] Serega the Pirate solution codeforces

Examples

input

Copy
3 3
2 1 3
6 7 4
9 8 5


output

Copy
0


input

Copy
2 3
1 6 4
3 2 5


output

Copy
1 3


input

Copy
1 6
1 6 5 4 3 2


output

Copy
2


## [Solution] Serega the Pirate solution codeforces

In the first example the sequence (1,2),(1,1),(1,2),(1,3),(2,3),(3,3)(1,2),(1,1),(1,2),(1,3),(2,3),(3,3)(2,3),(1,3),(1,2),(1,1),(2,1),(2,2),(3,2),(3,1)(2,3),(1,3),(1,2),(1,1),(2,1),(2,2),(3,2),(3,1) solves the puzzle, so the answer is 00.

The puzzle in the second example can’t be solved, but it’s solvable after any of three swaps of cells with values (1,5),(1,6),(2,6)(1,5),(1,6),(2,6).

The puzzle from the third example requires at least two swaps, so the answer is 22.