链接: https://cses.fi/problemset/task/1684

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

Uolevi 的家人打算一起点一个大披萨吃。共有 $n$ 名家庭成员参与点餐，有 $m$ 种可能的配料。披萨上可以有任意数量的配料。

每个家庭成员对披萨配料提出两个愿望。愿望形如“配料 $x$ 好/不好”。你的任务是选择配料，使得每个人至少有一个愿望成真（好的配料被包含在披萨中，或不好的配料未被包含）。

输入

第一行输入包含两个整数 $n$ 和 $m$：家庭成员数量和配料数量。配料编号为 $1,2,\dots,m$。

之后有 $n$ 行描述愿望。每行有两个形如 "+ $x$"（配料 $x$ 好）或 "- $x$"（配料 $x$ 不好）的愿望。

输出

输出一行 $m$ 个符号：对每个配料，包含则输出 "+"，不包含则输出 "-"。你可以输出任意合法解。

如果没有合法解，输出 "IMPOSSIBLE"。

数据范围

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

样例输入

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

样例输出

- + + + -