You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

普兰妮蓝岛（Pleniland）位于无尽网格图上。在岛上共有 $2n$ 座高塔：

• 其中 $n$ 座位于点 $(1, 1), (1, 2), (1, 3), \ldots, (1, n)$ 上；
• 其他 $n$ 座位于点 $(2, 1), (2, 2), (2, 3), \ldots, (2, n)$ 上。

以 $(1, 1), (1, n), (2, n), (2, 1)$ 为顶点的矩形称作是“市区”，市区之外的地方称作是“郊区”。

以上是 $n=7$ 时城市的示意图。

岛上的统治者决定用 $n$ 条道路把这些塔两两连线。对于每一个 $1\le i\le n$，他们希望把位于 $(1,i),(2,a_i)$ 上的两座塔连接起来。保证 $a_i$ 互不相同。

在岛上由于技术限制，只能修建两种道路：

1. “径”为完全位于市区的线段；
2. “曲”为完全位于郊区的曲线。

统治者还没有决定好该修建什么类型的路。请你判断是否存在一种修建计划，使得所有道路没有交点。注意：考虑到成本问题，“径”的位置仅由端点决定，而“曲”的位置与形状则是随意的。

输入格式

本题有多组数据。

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

接下来 $2\cdot T$ 行，描述每组数据。对于每组数据：

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数，即 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组数据，

• 若存在一组合法解，输出 $n$ 个以空格为分隔的整数 $b_1,b_2,\ldots,b_n\ (b_i\in\{1,2\})$。其中，$b_i=1$ 表示你选择用“径”修筑第 $i$ 条道路；$b_i=2$ 表示你选择用“曲”修筑第 $i$ 条道路；
• 否则，输出 $-1$。

输入输出样例

输入样例 1

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

输出样例 1

1 1 2
-1
1 1

样例 1 说明

对于数据 1，考察下列的方案：

• 图 A 展示了 $b=[1,1,2]$ 的情况。这是合法的，因为各道路并没有交点；
• 图 B 展示了 $b=[1,1,1]$ 的情况。这是非法的。
• 图 C 展示了 $b=[2,2,1]$ 的情况。这也是合法的。

对于数据 2，容易发现不存在对应的合法方案。

对于数据 3，方案 $[1,1]$, $[1,2]$, $[2,1]$, $[2,2]$ 均是合法的，因此你可以输出它们中的任何一个。

说明

Special Judge

本题开启 Special Judge。

数据规模与约定

对于所有数据，满足 $1\le T\le 10^4$，$2\le n\le 2\times10^5$，$1\le a_i\le n$ 且 $a_i$ 互不相同。

单个测试点内 $n$ 的总和不超过 $2\times 10^5$。