UOJ Logo Universal Online Judge

UOJ

#786. 【CTS2023】琪露诺的符卡交换

附件下载 统计

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

琪露诺调查之后,发现一共有 $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$ 种卡片。

样例一

input

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

output

2
1 3 3 1
2 3 3 2
0

explanation

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

第二次交换第二个人的第三张卡牌,和第三个人的第二张卡牌;

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

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

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

子任务

子任务 $1$($20$ 分):每个人只持有一种卡片。

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

子任务 $3$($60$ 分):无特殊限制。

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