CF741C Arpa’s overnight party and Mehrdad’s silent entering

Note that girls in Arpa’s land are really attractive. Arpa loves overnight parties. In the middle of one of these parties Mehrdad suddenly appeared. He saw $ n $ pairs of friends sitting around a table. $ i $ -th pair consisted of a boy, sitting on the $ a_{i} $ -th chair, and his girlfriend, sitting on the $ b_{i} $ -th chair. The chairs were numbered $ 1 $ through $ 2n $ in clockwise direction. There was exactly one person sitting on each chair. There were two types of food: Kooft and Zahre-mar. Now Mehrdad wonders, was there any way to serve food for the guests such that: - Each person had exactly one type of food, - No boy had the same type of food as his girlfriend, - Among any three guests sitting on consecutive chairs, there was two of them who had different type of food. Note that chairs $ 2n $ and $ 1 $ are considered consecutive. Find the answer for the Mehrdad question. If it was possible, find some arrangement of food types that satisfies the conditions.

N/A

N/A