3644. 后缀 Trie

单测试点时限: 3.0 秒

内存限制: 512 MB

Trie 是一种常见的数据结构。不知道 Trie 为何物的,请自行网搜。

若将一个长度为 的字符串的所有后缀(总共 个)插入一个 Trie 中,则称该 Trie 为字符串的后缀 Trie。

现以有根树的形式给出一个后缀 Trie,试问该树是否为一合法的后缀 Trie。如果是,求出原字符串。

输入

第一行一个整数 ,表示有 () 组测试数据。

每组测试数据有四行。第一行一个整数 (),表示树的节点个数。节点从 编号。

第二行 个整数 (),分别表示 的父亲节点的编号。由于节点 1 是根, 它没有父亲。

第三行是一个长度 的字符串 ,依次表示节点 到父亲节点的边上的字符。 是英文小写字母。

第四行是一个长度为 的 01 字符串 ,依次表示节点 是否是终态。 1 表示是, 0 表示不是。由于字符串的后缀不可能是空串,所以显然节点 1 不是终态。

另外,保证 组测试数据中的 的和不超过 ,且不存在两个节点 , 满足

本题数据量较大,请注意输入输出上的优化。

输出

对于每组测试数据,如果是合法的后缀 Trie,输出一行表示原字符串;如果不是,输出 Illegal

样例

Input
2
11
1 1 1 2 2 4 6 6 6 7
taioenadnn
0111011111
16
1 1 1 2 3 4 5 6 7 8 9 10 11 12 15
abnnaaannnaaana
100001100001101
Output
Illegal
banana

提示

下图对应样例 1 中的树。

下图对应样例 2 中的树。

18 人解决,31 已尝试。

22 份提交通过,共有 179 份提交。

8.4 EMB 奖励。

创建: 7 月前.

修改: 2 月,1 周前.

最后提交: 1 月,1 周前.

来源: EOJ Monthly 2018.10

标签