标签: 2-SAT

「CodeForces 1215F」 Radio Stations

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 𝑛.

「Usaco2011 Jan」奶牛议会

由于对Farmer John的领导感到极其不悦,奶牛们退出了农场,组建了奶牛议会。议会以“每头牛 都可以获得自己想要的”为原则,建立了下面的投票系统: MM只到场的奶牛 (1<=M<=4000)(1 <= M <= 4000) 会给N个议案投票(1<=N<=1,000)(1 <= N <= 1,000)。每只 奶牛会对恰好两个议案 BiandCi(1<=Bi<=N;1<=Ci<=N)B_i and C_i (1 <= B_i <= N; 1 <= C_i <= N)投 出“是”或“否”(输入文件中的'Y'和'N')。他们的投票结果分别为VBi(VBiinY,N)andVCi(VCiinY,N)VB_i (VB_i in {'Y', 'N'}) and VC_i (VC_i in {'Y', 'N'})。 最后,议案会以如下的方式决定:每只奶牛投出的两票中至少有一票和最终结果相符合。 例如Bessie给议案1投了赞成'Y',给议案2投了反对'N',那么在任何合法的议案通过 方案中,必须满足议案1必须是'Y'或者议案2必须是'N'(或者同时满足)。 给出每只奶牛的投票,你的工作是确定哪些议案可以通过,哪些不能。如果不存在这样一个方案, 输出"IMPOSSIBLE"。如果至少有一个解,输出: Y 如果在每个解中,这个议案都必须通过 N 如果在每个解中,这个议案都必须驳回 ? 如果有的解这个议案可以通过,有的解中这个议案会被驳回 考虑如下的投票集合: - - - - - 议案 - - - - - 1 2 3 奶牛 1 YES NO 奶牛 2 NO NO 奶牛 3 YES YES 奶牛 4 YES YES 下面是两个可能的解: * 议案 1 通过(满足奶牛1,3,4) * 议案 2 驳回(满足奶牛2) * 议案 3 可以通过也可以驳回(这就是有两个解的原因) 事实上,上面的问题也只有两个解。所以,输出的答案如下: YN?

「NOI2017」游戏

小 L 计划进行nn场游戏,每场游戏使用一张地图,小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆,分别用大写字母A、B、C表示。地图一共有四种,分别用小写字母x、a、b、c表示。其中,赛车A不适合在地图a上使用,赛车B不适合在地图b上使用,赛车C不适合在地图c上使用,而地图x则适合所有赛车参加。适合所有赛车参加的地图并不多见,最多只会有d张。

nn场游戏的地图可以用一个小写字母组成的字符串描述。例如:S=xaabxcbc表示小 L 计划进行88场游戏,其中第11场和第55场的地图类型是x,适合所有赛车,第22场和第33场的地图是a,不适合赛车A,第44场和第77场的地图是b,不适合赛车B,第66场和第88场的地图是c,不适合赛车C。

小 L 对游戏有一些特殊的要求,这些要求可以用四元组 (i, h_i, j, h_j)来描述,表示若在第 ii 场使用型号为hih_i 的车子,则第jj场游戏要使用型号为hjh_j
的车子。

你能帮小 L 选择每场游戏使用的赛车吗?如果有多种方案,输出任意一种方案。如果无解,输出 “-1’’(不含双引号)。

输入格式