School Excursion

题目描述

一群有 n 个孩子要来赫尔辛基。有两种可能的景点：孩子可以去 Korkeasaari（动物园）或 Linnanmäki（游乐园）。 有 m 对孩子希望去同一个景点。你的任务是找出所有可能的去 Korkeasaari 的孩子人数的备选方案。必须考虑孩子们的愿望。

输入格式

第一行输入包含两个整数 n 和 m：孩子的数量和他们的愿望。孩子编号为 1,2,\dots,n。 随后有 m 行描述孩子们的愿望。每行包含两个整数 a 和 b：孩子 a 和 b 希望去同一个景点。

输出格式

输出一个长度为 n 的二进制字符串，其中索引为 i 的一位为 1 表示恰好 i 个孩子去 Korkeasaari 是可能的（该二进制字符串按一索引考虑）。

5 3
1 2
2 3
1 5

10011

提示

$1 \le n \le 10^5$ $0 \le m \le 10^5$ $1 \le a,b \le n$ 样例解释：去 Korkeasaari 的孩子人数可以是 1、4 或 5。

标签: CSES1706|附加题2

来源

CSES1706|附加题2