[AdditionalFile5211.zip](file://AdditionalFile5211.zip?type=additional_file)

#5211. 「UOI 2024 Stage 4 Day1」送给莱蒂的礼物

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2024 Stage 4 Day1 T2. Подарунок Леді

在生日当天，莱蒂收到了一份礼物——一个网络。这个网络包含 $n$ 个节点，编号为从 $1$ 到 $n$ 的整数。每个节点上写有一个字母，对于编号为 $i$ 的节点，其字母记为 $s_i$。

某些节点之间存在单向连接。每个节点恰好有一个单向连接指向另一个节点。设从编号为 $i$ 的节点出发的连接指向编号为 $x_i$ 的节点。注意，$x_i$ 可以等于 $i$，即从节点 $i$ 出发的连接指向它自身。

定义 $p_{i,0} = i$，且 $p_{i,k} = p_{x_i,k-1}$。也就是说，$p_{i,k}$ 是将棋子放在编号为 $i$ 的节点上，并沿连接移动 $k$ 次后到达的节点编号。

莱蒂创建了一个 $n \times (3 \cdot n)$ 的矩阵 $a$，其中 $a_{i,j} = s_{p_{i,j-1}}$。也就是说，矩阵 $a$ 的第 $i$ 行是长度为 $3 \cdot n$ 的字母序列，其第一个字母为 $s_i$，第二个字母为 $s_{x_i}$，第三个字母为 $s_{x_{x_i}}$，依此类推……

莱蒂提供了矩阵 $a$ 的某些行，并要求你构建一个符合这些已知行的网络。

输入格式

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 2 \cdot 10^3)$，表示网络中节点的数量。

接下来的 $n$ 行描述矩阵 $a$。每行包含 $3 \cdot n$ 个小写拉丁字母，表示矩阵 $a$ 的对应行；或者包含一个字符 ?，表示莱蒂未提供该行信息。

保证至少存在一个符合条件的网络。

输出格式

输出第一行包含一个长度为 $n$ 的小写拉丁字母字符串 $s$，表示网络节点上写着的字母。

输出第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$ $(1 \leq x_i \leq n)$，表示从对应节点出发的连接指向的节点编号。

所构建的网络对应的矩阵必须在莱蒂提供的每一行上与矩阵 $a$ 一致。

如果存在多个正确答案，可以输出任意一个。

样例 1

输入

4
abaaaaaaaaaa
baaaaaaaaaaa
aaaaaaaaaaaa
cccccccccccc

输出

abac
2 3 3 4

在第一个样例中，$x_1 = 2$ 且 $x_2 = 3$，因此 $p_{1,0}=1, p_{1,1}=2, p_{1,2}=3$。由于 $x_3=3$，对于 $k \geq 3$ 的所有 $p_{1,k}$ 也等于 $3$。因此，第一个行的第二个字母为 $s_2$，第三个字母为 $s_3$。

以下是样例中的网络图示。节点角落中的数字表示节点编号，字母表示节点上写的值，箭头表示单向连接。

样例 2

输入

3
axaxaxaxa
xxxxxxxxx
?

输出

axx
3 2 1

数据范围与提示

设 $q$ 为莱蒂未提供的行数。

定义网络为成对和单节点集合，如果网络可以分解为一些节点（其中 $x_v = v$，即连接指向自身）和一些节点对 $(a, b)$（其中 $x_a = b$ 且 $x_b = a$）。

定义网络为星形集合，如果网络可以分解为若干「星形」，每个星形包含一个中心节点 $v$（其中 $x_v = v$，即连接指向自身）和一组次级节点 $y = \{y_1, y_2, \ldots, y_k\}$（其中对于 $1 \leq i \leq k$，有 $x_{y_i} = v$）。注意，星形的规模可以不同，也可以仅包含一个中心节点。

定义网络为以节点 $v$ 为根的树，如果节点 $v$ 的连接指向自身（即 $x_v = v$），且对于其他所有节点，可以通过网络连接到达节点 $v$（即对于每个 $1 \leq i \leq n$，存在 $k$ 使得 $p_{i,k} = v$）。

定义网络为循环，如果从任意节点出发，可以通过网络连接到达任意其他节点（即对于所有 $1 \leq i,j \leq n$，存在 $k$ 使得 $p_{i,k} = j$）。

详细子任务附加限制及分值如下表所示：