You are at a pizzeria with n toppings. M customers each specify two toppings they want: one with + (on the pizza) or - (not on the pizza). Each customer needs at least one of their two wishes satisfied. Can you choose which toppings to add so every customer is happy?
This is -SAT in disguise. The input gives you n toppings and m customers. Each customer line has four values: sign1, topping1, sign2, topping2. The signs are + or -. You output a solution string if one exists, or "IMPOSSIBLE" if not.