Giant Pizza

题目描述

Uolevi的家人要订一个大披萨一起吃。共有n位家庭成员参加点单，且有m种可能的配料。披萨可以有任意数量的配料。 每位家庭成员对披萨的配料都给出两个愿望。愿望的形式为“配料 x 是喜欢/不喜欢”。你的任务是选择配料使得每个人至少有一个愿望成为真的（喜欢的配料被加入披萨或不喜欢的配料未被加入）。

输入格式

第一行输入包含两个整数 n 和 m：家庭成员数和配料数。配料编号为 1,2,\dots,m。 随后有 n 行描述这些愿望。每行包含两个愿望，形式为 "+ x"（配料 x 是喜欢的）或 "- x"（配料 x 是不喜欢的）。

输出格式

输出一行包含 m 个符号：对于每种配料，如果被加入则输出 "+"，否则输出 "-"。你可以输出任意一个满足条件的解。 如果不存在满足条件的解，输出 "IMPOSSIBLE"。

3 5
+ 1 + 2
- 1 + 3
+ 4 - 2

- + + + -

提示

$1 \le n,m \le 10^5$ $1 \le x \le m$

标签: CSES1684|图论

来源

CSES1684|图论