#P6286. [COCI2016-2017#1] Cezar

    ID: 5303 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>字符串2016Special Judge拓扑排序字典树,TrieCOCI

[COCI2016-2017#1] Cezar

题目描述

Mirko 想对 nn 个单词进行加密。加密过程是这样的:

  1. 选择一个英文字母表的排列作为密钥。
  2. 将单词中的 a 替换为密钥中的第一个字母,b 替换为密钥中的第二个字母……以此类推。

例如,以 qwertyuiopasdfghjklzxcvbnm 作为密钥对 cezar 加密后,将得到 etmqk

他希望,将所有单词加密并按字典序升序排列后,最初的第 aia_i 个单词位于第 ii 位。请你判断,这能否实现。如果能,请给出任意一种可行的密钥。

输入格式

第一行一个整数 nn

接下来 nn 行,每行一个字符串,表示待加密的单词。

最后一行 nn 个整数,表示 aia_i

输出格式

本题使用 Special Judge

如果 Mirko 的要求不能实现,输出 NE

否则,输出 DA。接下来一行输出任意一种可行的密钥。

2
ab
bc
2 1 
DA
bacdefghijklmnopqrstuvwxyz 
3
abc
bcd
add
1 2 3 
NE 
3
bbb
ccc
ddd
2 3 1 
DA
adbcefghijklmnopqrstuvwxyz 

提示

【样例解释】

样例 1 解释

bacdefghijklmnopqrstuvwxyz 为密钥加密后,得到:

  • ba
  • ac

字典序升序排列后,得到:

  • ac
  • ba

原先的第一个单词在第二位,第二个单词在第一位。符合要求。

样例 3 解释

adbcefghijklmnopqrstuvwxyz 为密钥加密后,得到:

  • ddd
  • bbb
  • ccc

字典序升序排列后,得到:

  • bbb
  • ddd
  • ccc

原先的第一个单词在第二位,第二个单词在第三位,第三个单词在第一位。符合要求。


数据规模与约定

对于 100%100\% 的数据,2n1002\le n\le 1001ain1 \leq a_i \leq n

所有单词的长度不超过 100100,且只包含小写字母。


说明

题目译自 COCI2016-2017 CONTEST #1 T3 Cezar