## 标签: 2-SAT

In addition to complaints about lighting, a lot of complaints about insufficient radio signal covering has been received by Bertown city hall recently. 𝑛 complaints were sent to the mayor, all of which are suspiciosly similar to each other: in the 𝑖-th complaint, one of the radio fans has mentioned that the signals of two radio stations 𝑥𝑖 and 𝑦𝑖 are not covering some parts of the city, and demanded that the signal of at least one of these stations can be received in the whole city.

## 「CodeForces 1250E」 The Coronation

The coronation of King Berl XXII is soon! The whole royal family, including 𝑛 daughters of Berl XXII, will be present.

The King has ordered his jeweler to assemble 𝑛 beautiful necklaces, so each of the princesses could wear exactly one necklace during the ceremony — and now these necklaces are finished. Each necklace consists of 𝑚 gems attached to a gold chain. There are two types of gems used in the necklaces — emeralds and sapphires. So, each necklace can be represented by a sequence of 𝑚 gems (listed from left to right), and each gem is either an emerald or a sapphire. Formally, the 𝑖-th necklace can be represented by a binary string 𝑠𝑖 of length 𝑚; if the 𝑗-th character of 𝑠𝑖 is 0, then the 𝑗-th gem in the 𝑖-th necklace is an emerald; otherwise, this gem is a sapphire.

## 「CodeForces 1239D」Catowice City

In the Catowice city next weekend the cat contest will be held. However, the jury members and the contestants haven't been selected yet. There are 𝑛 residents and 𝑛 cats in the Catowice, and each resident has exactly one cat living in his house. The residents and cats are numbered with integers from 1 to 𝑛, where the 𝑖-th cat is living in the house of 𝑖-th resident.

Each Catowice resident is in friendship with several cats, including the one living in his house. In order to conduct a contest, at least one jury member is needed and at least one cat contestant is needed. Of course, every jury member should know none of the contestants. For the contest to be successful, it's also needed that the number of jury members plus the number of contestants is equal to 𝑛.

## 「NOI2017」游戏

$n$场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbc表示小 L 计划进行$8$场游戏，其中第$1$场和第$5$场的地图类型是x，适合所有赛车，第$2$场和第$3$场的地图是a，不适合赛车A，第$4$场和第$7$场的地图是b，不适合赛车B，第$6$场和第$8$场的地图是c，不适合赛车C。