[AdditionalFile3928.zip](file://AdditionalFile3928.zip?type=additional_file)

#3928. 「CTS2023」琪露诺的符卡交换

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

受异变的影响，琪露诺发现封印了自己能力的卡片正在幻想乡中流通。

琪露诺调查之后，发现一共有 $n$ 种不同的卡片，每种卡片的数量总共恰好是 $n$ 张，有 $n$ 个人购买了这些卡片，每个人都恰好买了 $n$ 张卡片，并且可能会买到相同种类的卡片。

但是琪露诺想要让每个人都正好持有 $n$ 种卡片，于是她把这 $n$ 个人聚集在一起，想要通过卡片交换的形式达成她的目的。

琪露诺每次会选择两个人持有的某张卡片进行交换，直到每个人都正好持有 $n$ 种卡片为止。

由于每次交换都会减少卡片上的魔力，所以琪露诺想要每张卡片最多被交换一次。

但是她对如何进行交换犯了难，于是她转而寻求你的帮助。

你需要告诉她交换的过程，或者告诉她不存在这样的方案。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行一个正整数 $n$，含义如题所示。

接下来 $n$ 行，每行输入 $n$ 个正整数，其中第 $i$ 行的第 $j$ 个正整数表示第 $i$ 个人持有的第 $j$ 张卡片的种类。

输出格式

对于每组数据，如果不存在能够让每个人都持有 $n$ 种卡片的方案，输出一行 -1

否则首先输出一行一个正整数 $m$，表示交换次数。

接下来 $m$ 行，每行输出四个正整数 $a,b,c,d$，表示第 $a$ 个人的第 $b$ 张卡片，与第 $c$ 个人的第 $d$ 张卡片进行一次交换。

注意你需要保证不存在某张卡片被交换了两次，并且交换结束后每个人都正好持有 $n$ 种卡片。

样例 1

输入

2
3
1 2 2
2 3 3
3 1 1
3
1 2 3
2 3 1
3 2 1

输出

2
1 3 3 1
2 3 3 2
0

第一组数据，我们第一次交换第一个人的第三张卡牌，和第三个人的第一张卡牌；

第二次交换第二个人的第三张卡牌，和第三个人的第二张卡牌；

一共交换两次，可以使得所有人都持有三种卡牌。

输出其它方案也是被允许的。

第二组数据，因为一开始所有人都持有了三种卡牌，所以无需交换，输出一行 0 即可。

数据范围与提示

子任务 $1$（$20$ 分）：每个人只持有一种卡片。

子任务 $2$（$20$ 分）：每个人持有至少 $n-1$ 张同一种类的卡片。

子任务 $3$（$60$ 分）：无特殊限制。

对于所有数据，满足 $\sum\limits_{i=1}^{T}n_{i} \leq 200$。