棋盘翻转

题目描述

一个 $n \times n$ 的棋盘上放有 $n$ 辆车，满足棋子之间不会互相攻击，即每行列只有一个车。而 ws.hcl 认为整齐的排列是对齐的，即第 $i$ 列的车应该处于第 $i$ 行。

定义一次操作为：选择一段列的区间 $[l, r]$，并将这些列沿区间 $[l, r]$ 的中轴左右翻转，代价为区间长度 $r - l + 1$。

定义操作的总代价为每次操作代价的按位异或和，需要用若干次操作使满足 ws.hcl 要求。

求所有可行方案中总代价的最小值和最大值。

输入格式

从文件 board.in 中读入数据。

第一行一个整数 $T$ 表示数据组数。接下来依次描述各组数据。 对于每组数据：

• 第一行一个整数 $n$，表示棋盘的边长及车的数量。
• 接下来 $n$ 行，每行 $2$ 个整数，分别表示每个车的坐标。

输出格式

输出到文件 board.out 中。

对于每组数据，输出一行两个整数，分别表示总代价的最小值和最大值。

样例 #1

样例输入 #1

1
6
1 4
2 6
3 5
4 3
5 1
6 2

样例输出 #1

0 5

样例解释 #1

• 最小价值：翻转 $[4,5]$、$[3,4]$、$[5,6]$、$[4,5]$ 即可，代价为 $2 \oplus 2 \oplus 2 \oplus 2 = 0$。
• 最大价值：翻转 $[3,6]$、$[3,4]$、$[5,6]$、$[1,1]$ 即可，代价为 $4 \oplus 2 \oplus 2 \oplus 1 = 5$。

样例 #2

见附加文件中的 farm2.in 和 farm2.ans。

数据范围

对于所有数据：

• $T \le 5$
• $n \le 5 \times 10^5$
• 保证给出的坐标合法。

测试点分布表