← 返回题目列表

Codeforces · 780/D

D. Innokenty 和足球联赛

中文机器翻译题面 查看原题

Innokenty 是 Byteland 一个新足球联盟的主席。他要做的第一个任务是为所有俱乐部分配短名称,以便在电视上的比分旁边显示。当然,短名称应该是不同的,Innokenty 希望所有短名称都由三个字母组成。

每个俱乐部的全名由两个单词组成:球队名称和家乡名称,例如“DINAMO BYTECITY”。 Innokenty 不想指定奇怪的短名称,因此他想为每个俱乐部选择这样的短名称:

1. 简称与球队名称的前三个字母相同,例如,对于上述俱乐部来说是“DIN”,
2. 或者,简称的前两个字母应与球队名称的前两个字母相同,第三个字母与家乡名称的第一个字母相同。对于提到的俱乐部,它是“DIB”。

除此之外,还有一条规则,如果对于某个俱乐部 x 选择了第二个短名称选项,则不应有任何俱乐部选择第一个选项与俱乐部 x 的第一个选项相同。例如,如果上述俱乐部具有简称“DIB”,则选择第一个选项的俱乐部都不能具有等于“DIN”的简称。不过,有可能一些俱乐部的简称为“DIN”,其中“DI”是球队名称的前两个字母,“N”是家乡名称的第一个字母。当然,任何两支球队不能有相同的简称。

帮助 Innokenty 为每个团队选择一个简称。如果这是不可能的,请报告。如果有多个答案,那么任何一个都适合 Innokenty。如果对于某个团队来说,两个短名称选项是相同的,那么 Innokenty 将正式认为只选择了其中一个选项。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1000) — 联赛中的俱乐部数量。

接下来的 n 行中的每一行都包含两个单词 - 球队的名称和某个俱乐部家乡的名称。球队名称和家乡名称均由大写英文字母组成,长度最少为3,最多为20。

输出

不可能选择短名称并满足所有约束,打印一行“NO”。

否则,在第一行打印“YES”。然后打印n行,在每行中打印所选的相应俱乐部的简称。按照输入中出现的顺序打印俱乐部。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

2
DINAMO BYTECITY
FOOTBALL MOSCOW

输出 #1

YES
DIN
FOO

输入 #2

2
DINAMO BYTECITY
DINAMO BITECITY

输出 #2

NO

输入 #3

3
PLAYFOOTBALL MOSCOW
PLAYVOLLEYBALL SPB
GOGO TECHNOCUP

输出 #3

YES
PLM
PLS
GOG

输入#4

3
ABC DEF
ABC EFG
ABD OOO

输出#4

YES
ABD
ABE
ABO

注意

在第一个样本中,Innokenty 可以为两个俱乐部选择第一个选项。

在第二个示例中,不可能选择短名称,因为如果两个俱乐部的第一个选项相同,则一个俱乐部不可能有第一个选项,而另一个俱乐部有第二个选项。

在第三个示例中,Innokenty 可以为前两个俱乐部选择第二个选项,为第三个俱乐部选择第一个选项。

在第四个示例中,请注意,如果 x 和 y 的第一个选项不同,则某些俱乐部 x 所选择的简称可能与另一个俱乐部 y 的第一个选项相同。