#P16102. [Oni2016]transform

    ID: 15313 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-二分图建模无向连通分量不变量分析置换直接模拟

[Oni2016]transform

题目描述

一个 N×NN\times N 的 0/10/1 矩阵称为“Calafat 矩阵”,当且仅当它满足:

  • 每一行恰好有两个 11;
  • 每一列恰好有两个 11;
  • 其它位置均为 00。

现在给定两个这样的矩阵 AA 和 BB。你需要通过交换矩阵 BB 的若干行和若干列,将 BB 变成 AA。

题目保证所有输入数据均有解。

输入格式

第一行包含整数 NN,表示矩阵大小。

接下来 2N2N 行,每行两个整数 x,yx,y,表示矩阵 AA 中一个值为 11 的元素位置为第 xx 行第 yy 列。

再接下来 2N2N 行,每行两个整数 x,yx,y,表示矩阵 BB 中一个值为 11 的元素位置为第 xx 行第 yy 列。

输出格式

每行输出一个操作,格式为:

ch x y

其中 ch 只能为 L、C 或 0:

  • 若 ch = L,表示交换矩阵 BB 的第 xx 行和第 yy 行;
  • 若 ch = C,表示交换矩阵 BB 的第 xx 列和第 yy 列;
  • 最后一行必须输出:
0 0 0

表示操作结束。

数据范围与评分

  • 1≤N≤800001\le N\le 80000;
  • 题目保证存在解。

设实际执行的交换操作数为 opop,不计最后的 0 0 0。若输出正确,则按如下规则给分:

  • 1≤op≤2N1\le op\le 2N:获得 100%100\% 分数;
  • 2N+1≤op≤4N2N+1\le op\le 4N:获得 75%75\% 分数;
  • op>4Nop>4N:获得 50%50\% 分数。

样例

输入

4
1 1
2 2
3 3
4 1
3 4
4 4
2 3
1 2
1 3
2 3
1 1
2 2
4 2
4 4
3 4
3 1

输出

L 3 4
C 3 2
0 0 0

样例解释

先读入矩阵 AA:

1 1 0 0
0 1 1 0
0 0 1 1
1 0 0 1

再读入矩阵 BB:

1 0 1 0
0 1 1 0
1 0 0 1
0 1 0 1

交换第 33 行与第 44 行后,再交换第 33 列与第 22 列,即可得到矩阵 AA。