1-SAT

题目描述

给定 $N$ 个字符串 $S_1, S_2, \dots, S_N$。 每个字符串都是由小写英文字母构成的非空字符串，并且在开头可能有也可能没有一个 $!$。
当字符串 $T$ 与 $S_1, S_2, \dots, S_N$ 中的某个字符串匹配时（不管是否在 $T$ 的开头添加了 $!$），我们称 $T$ 为不满足的（unsatisfied）。
判断是否存在一个不满足的字符串。如果存在，给出一个这样的字符串。

输入格式

输入由标准输入给出，格式如下： $N$ $S_1$ $\vdots$ $S_N$

输出格式

如果存在不满足的字符串，输出其中一个。
如果不存在不满足的字符串，输出 $satisfiable$。

6
a
!a
b
!c
d
!d

a

10
red
red
red
!orange
yellow
!blue
cyan
!green
brown
!gray

satisfiable

提示

$1 \le N \le 2 \times 10^5$ $1 \le |S_i| \le 10$ $S_i$ 是由小写英文字母构成的非空字符串，并且在开头可能有也可能没有一个 $!$。$a$ 作为原样与 $S_1$ 匹配，同时当我们在前面加上 $!$ 时与 $S_2$ 匹配，因此它是不满足的。 除此之外，$d$ 也被接受。

标签: AtCoder|abc187C

来源

AtCoder|abc187C