UOJ Logo Universal Online Judge

UOJ

#670. 【UNR #5】获奖名单

附件下载 统计

UOI 终于考完了,现在你要以标准的宇宙通用语请获奖选手上台领奖。

现在邀请的这一批选手一共有 $n$ 个“人”。更准确地说,他们是一群脑回路几乎相同的外星蜜蜂,故而在比赛中取得了完全相同的分数。

宇宙通用语非常强大,一共有 $m$ 种符号。用这种语言表达每只外星蜜蜂的名字要么只需要一个符号,要么只需要两个符号。

你需要给这一批选手编写一份由他们所有人名字组成的获奖名单,再按顺序念出来。你可以做如下调整:

  1. 你可以调整这 $n$ 个名字的排列顺序;
  2. 由于外星蜜蜂的特殊文化,所有两个符号的名字无论你顺着念还是倒着念,指代的都是同一只蜜蜂。所以名单中每个两个符号的名字你既可以按顺序写也可以按逆序写。
  3. 可能存在名字相同的多只蜜蜂,但你仍然要读这个名字多次。

为了避免倾向性,你希望最后把名字顺次连起来是个回文串。也就是说,你要让名字串起来后的符号序列从左到右读和从右往左读没有区别。

测试数据保证有解。

输入格式

第一行两个正整数 $n,m$,分别表示选手个数和符号数。选手从 $1 \ldots n$ 编号。

接下来 $n$ 行,第 $i$ 行先输入一个正整数 $l_i \in \{1,2\}$ 表示 $i$ 号选手的名字长度,下面 $l_i$ 个 $1 \sim m$ 间的整数,表示第 $i$ 个人的名字。

输出格式

第一行输出由 $n$ 个 $1\sim n$ 的整数组成的排列,第 $i$ 个为 $p_i$,表示最后名单的第 $i$ 个选手是 $p_i$ 号选手。

下一行输出 $n$ 个 $01$ 整数,第 $i$ 个为 $0$ 表示 $p_i$ 号选手的名字正着写(与输入顺序一致),为 $1$ 表示倒着写。

注意,如果 $p_i$ 号选手名字长度为 $1$,你可以随便输出 $0$ 或 $1$。如果有多种合法的获奖名单,你可以任意输出一个。

样例一

input

4 2
2 1 1
2 1 2
1 1
1 2

output

4 1 3 2 
0 1 0 0 

explanation

样例一输出对应的回文串是 $211112$。

样例二

input

2 2
1 1
2 1 2

output

1 2 
0 1 

explanation

样例二输出对应的回文串是 $121$。

样例三

见附加文件中 ex_namelist3.inex_namelist3.out,该组样例满足子任务 5 的性质。

样例四

见附加文件中 ex_namelist4.inex_namelist4.out,该组样例满足子任务 6 的性质。

样例五

见附加文件中 ex_namelist5.inex_namelist5.out,该组样例满足子任务 5 的性质。

限制与约定

对于 $100\%$ 的数据,$1\leq n,m\leq 5\times 10^5$。令 $L=\sum_{i=1}^{n} l_i$。

子任务编号 $n,m\le$ 特殊性质 分值
$1$ $10$ $15$
$2$ $20$ $20$
$3$ $5\times 10^5$ $l_i=2$ $10$
$4$ $3000$ $15$
$5$ $5\times 10^5$ $L$ 为偶数
$6$ $L$ 为奇数
$7$ $10$

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$