题目描述
有人说,它拯救了世界;也有人说,它毁灭了世界。
这个世界危在旦夕!秩序已然一片混乱。
秩序可以抽象成一个 n×n 的矩阵,矩阵中是一个 1∼n2 的排列。你想要拯救世界,于是请来了神,来帮忙把秩序恢复原状。然而神也不是万能的,它只能做到交换矩阵中同一行或者同一列中的两个数。而且,它并不知道要怎么交换才能复原,得听你的指导。
幸好,你不一定需要在最少的交换次数之内完成复原。你只需要不比最糟糕的情况差就好。也就是说,如果你的交换次数为 k,且对于所有 1∼n2 的排列,最小交换次数的最大值为 k0,你只需要满足 k≤k0。
注:复原指的是将矩阵变为如下的一个矩阵:
123⋯nn+1n+2n+3⋯2n2n+12n+22n+3⋯3n⋮⋮⋮⋱⋮(n−1)n+1(n−1)n+2(n−1)n+3⋯n2
输入格式
第一行一个正整数 n。
接下来 n 行,每行 n 个正整数,表示这个 n×n 的矩阵。保证 1∼n2 中的每个数恰好出现一次。
输出格式
第一行一个非负整数 k,表示你的交换次数。
接下来 k 行,每行四个正整数 x1,y1,x2,y2,表示将第 x1 行 y1 列的数与第 x2 行 y2 列的数交换。
你需要保证 x1=x2 或 y1=y2。
样例数据
样例 1 输入
2
4 2
3 1
样例 1 输出
3
1 1 1 2
1 2 2 2
1 1 1 2
样例 1 解释
可以证明这是交换次数最少的方案之一,显然它符合条件。
样例 2 输入
2
2 1
3 4
样例 2 输出
3
2 1 2 2
1 1 1 2
2 1 2 2
样例 2 解释
对于这个输入来说,这个样例输出的方案不是交换次数最少的方案,但是我们知道存在一个 1∼n2 的排列(即上一个样例)需要至少 3 次的交换,所以这个方案也是可行的。
样例 3 输入
2
3 2
1 4
样例 3 输出
2
1 1 1 1
1 1 2 1
样例 3 解释
我们允许出现 (x1,y1)=(x2,y2) 的情况。
样例 4 输入
2
1 2
3 4
样例 4 输出
0
样例 4 解释
注意 k 可以等于 0。
子任务
保证 1≤n≤1000。
保证输入的矩阵中 1∼n2 恰好各出现一次。