import Control.Applicative -- this is needed for <$> as the ideone Haskell version ist not up-to date
t=1<3
e
%((t
,f
):r
)=or((e
<$>t
)++map(not.e
)f
)&&e
%r
e%_=t
u v b e s|s==v=b|t=e s
s e[]c=1<0
s e(v:w)c=e%c||s(u v t e)w c||s(u v(1<0)e)w c
g v[]=v
g v
((t
,f
):r
)=g
(v
++[x
|x
<-t
++f
,notElem x v
])r
isSat = g[]>>=s(\x->t)
test = (isSat[(["A","B"],[])] == True)
&& (isSat[([],["B"]),(["A","B"],[])] == True)
&& (isSat[([],["B"]),(["B"],[])] == False)
&& (isSat[(["P"],["Q","R"]),(["Q","R"],["P"]),(["Q"],["P","R"])] == True)
&& (isSat[([],["P"]),(["S"],[]),(["R"],["P"]),(["U"],["Q"]),(["X"],["R"]),(["Q"],["S"]),([],["P","U"]),(["W"],["Q","U"])] == True)
&& (isSat[([],["P","Q"]),(["Q","P"],[]),(["P"],["Q"]),(["Q"],["P"])] == False)
&& (isSat[(["P"],[]),([],["P","S"]),(["P","T"],[]),(["Q"],["R"]),([],["R","S"]),([],["P","Q","R"]),([],["P"])] == False)
aW1wb3J0IENvbnRyb2wuQXBwbGljYXRpdmUgLS0gdGhpcyBpcyBuZWVkZWQgZm9yIDwkPiBhcyB0aGUgaWRlb25lIEhhc2tlbGwgdmVyc2lvbiBpc3Qgbm90IHVwLXRvIGRhdGUKCm1haW4gPSBwdXRTdHIoc2hvdyB0ZXN0KQoKdD0xPDMKZSUoKHQsZik6cik9b3IoKGU8JD50KSsrbWFwKG5vdC5lKWYpJiZlJXIKZSVfPXQKdSB2IGIgZSBzfHM9PXY9Ynx0PWUgcwpzIGVbXWM9MTwwCnMgZSh2OncpYz1lJWN8fHModSB2IHQgZSl3IGN8fHModSB2KDE8MCllKXcgYwpnIHZbXT12CmcgdigodCxmKTpyKT1nKHYrK1t4fHg8LXQrK2Ysbm90RWxlbSB4IHZdKXIKCmlzU2F0ID0gZ1tdPj49cyhceC0+dCkKCnRlc3QgPSAoaXNTYXRbKFsiQSIsIkIiXSxbXSldID09IFRydWUpIAogJiYgKGlzU2F0WyhbXSxbIkIiXSksKFsiQSIsIkIiXSxbXSldID09IFRydWUpIAogJiYgKGlzU2F0WyhbXSxbIkIiXSksKFsiQiJdLFtdKV0gPT0gRmFsc2UpCiAmJiAoaXNTYXRbKFsiUCJdLFsiUSIsIlIiXSksKFsiUSIsIlIiXSxbIlAiXSksKFsiUSJdLFsiUCIsIlIiXSldID09IFRydWUpIAogJiYgKGlzU2F0WyhbXSxbIlAiXSksKFsiUyJdLFtdKSwoWyJSIl0sWyJQIl0pLChbIlUiXSxbIlEiXSksKFsiWCJdLFsiUiJdKSwoWyJRIl0sWyJTIl0pLChbXSxbIlAiLCJVIl0pLChbIlciXSxbIlEiLCJVIl0pXSA9PSBUcnVlKSAKICYmIChpc1NhdFsoW10sWyJQIiwiUSJdKSwoWyJRIiwiUCJdLFtdKSwoWyJQIl0sWyJRIl0pLChbIlEiXSxbIlAiXSldID09IEZhbHNlKSAKICYmIChpc1NhdFsoWyJQIl0sW10pLChbXSxbIlAiLCJTIl0pLChbIlAiLCJUIl0sW10pLChbIlEiXSxbIlIiXSksKFtdLFsiUiIsIlMiXSksKFtdLFsiUCIsIlEiLCJSIl0pLChbXSxbIlAiXSldID09IEZhbHNlKQ==