#P6036. 「雅礼集训 Day4」编码

「雅礼集训 Day4」编码

说明

Bob\text{Bob} 最新学习了一下二进制前缀编码的那一套理论。二进制编码是指一个由 nn 个互不相同的二进制串 s1,s2,…,sns_1,s_2,\ldots,s_n 构成的集合。而如果一套编码理论满足,对于任意的 i≠ji \neq j ,sis_i 不是 sjs_j 的前缀,那么我们称它为前缀编码。

Bob\text{Bob} 发现了一张上面写有 nn 行二进制编码的纸,但这张纸年代久远,有些字迹已经模糊不清。幸运的是,每一行至多只会有一个模糊的字符。

Bob\text{Bob} 想知道这 nn 行二进制编码是否有可能是一个前缀编码?

输入格式

第一行一个整数 n n,表示编码的大小。 接下来 nn 行,每行一个由0,10,1及?组成的字符串。保证每一行至多有一个?。

输出格式

如果这 nn 个二进制编码可能是前缀编码,输出YES,否则输出NO。

样例

4
00?
0?00
?1
1?0
YES

提示

本题采用捆绑测试。

你需要通过一个子任务内的所有测试点才能得到该子任务的分数。

子任务 分值 nn 字符串总长
11 2020 ≤10\le 10 ≤1000\le 1000
22 3030 ≤1000\le 1000 ≤500000\le 500000
33 $ 50$ $ \le 500000$