1002. B. Binary Choice

题目描述

本题开启 Special Judge

给定 (n) 个三元组：

其中 (a_i,b_i) 是第 (i) 个位置的两个候选值，(c_i) 是它的颜色。

你需要对每个位置 (i)：

1. 从 (a_i,b_i) 中选择一个作为最终值 (x_i)；
2. 将该位置放入第 (0) 组或第 (1) 组。

要求同时满足：

• 对于每种颜色，两组中这种颜色的数量相等；
• 对于每种值，两组中这个值的数量相等。

输入保证每种颜色出现偶数次。

样例解释

第一组中最终选择的值依次为 (2,2,1,1)。颜色 (10,20) 和最终值 (1,2) 都分别在两组中出现一次。

第二组中，值 (1) 和值 (2) 都只能被选择一次，不可能在两组中平分，因此无解。

数据范围

• (1\le T\le 10)
• (2\le n\le 2\times10^5)
• 对于所有测试数据，(n) 之和不超过 (4\times10^5)
• (1\le a_i,b_i,c_i\le10^9)
• 每种颜色的出现次数均为偶数

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 (n)，表示三元组的数量；
• 接下来 (n) 行，第 (i) 行包含三个整数 (a_i,b_i,c_i)，分别表示第 (i) 个位置的两个候选值和颜色。

输出格式

对于每组测试数据：

• 如果不存在合法方案，输出一行 -1；
• 否则输出两行长度均为 (n) 的 01 字符串 (s,t)。

其中：

• (s_i=0) 表示选择 (a_i)，(s_i=1) 表示选择 (b_i)；
• (t_i) 表示位置 (i) 被放入的组号。

如果存在多组合法方案，输出任意一组即可。

样例输入

2
4
1 2 10
2 3 10
1 1 20
1 1 20
2
1 1 7
2 2 7

样例输出

1000
0101
-1

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1002 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。