#P4840. [Neerc2016]Binary Code

    ID: 3959 传统题 1000ms 512MiB 尝试: 17 已通过: 6 难度: 9 上传者: 标签>CF2600省选/NOI-2-SATTrie辅助点压缩边Tarjan 强连通分量算法SCC 判定可满足性

[Neerc2016]Binary Code

题目描述

给定 n 个01串,每个字符串至多有一位是未知的,可以填 0 或 1 ,求是否存在一种方案,使得任意一个字符串不是其它任意一个字符串的前缀

输入格式

第一行是一个正整数 n ,代表字符串的数量。 (1≤n≤5⋅105)(1 \leq n \leq 5 \cdot 10^5)

接下来 n 行每行一个字符串,只可能由 0 、 1 或 ? 组成。 ? 代表未知的位置,每个字符串最多一个。

保证字符串总长度不超过 5⋅1055 \cdot 10^5 。

输出格式

如果无解,只需要输出 NO 。

如果有解,在第一行输出 YES ,接下来 n 行输出方案。

如果有多组解,只需要输出任意一组。

输入输出样例 #1

输入 #1

4
00?
0?00
?1
1?0

输出 #1

YES
000
0100
11
100

输入输出样例 #2

输入 #2

3
0100
01?0
01?0

输出 #2

NO