7441. 学校远足 (School Excursion)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 学校远足 (School Excursion) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 一个由 $n$ 个孩子组成的团体来到了赫尔辛基。这里有两个可选的景点：孩子们可以去 Korkeasaari（动物园）或者 Linnanmäki（游乐园）。 已知有 $m$ 对孩子，每对孩子都希望去同一个景点。在必须满足这些愿望的前提下，您的任务是找出所有可能去 Korkeasaari 的总孩子人数。 ## 输入格式 第一行包含两个整数 $n$ 和 $m$：孩子的数量和他们的愿望数量。孩子们的编号为 $1, 2, \dots, n$。 接下来的 $m$ 行描述了孩子们的愿望。每行包含两个整数 $a$ 和 $b$：代表孩子 $a$ 和孩子 $b$ 必须去同一个景点。 ## 输出格式 输出一个长度为 $n$ 的 01 字符串。若在第 $i$ 位（下标从 $1$ 开始）为 `1`，则表示恰好有 $i$ 个孩子去 Korkeasaari 是可行的；若为 `0`，则表示不可能。 ## 输入输出样例 ### 输入 #1 ```text 5 3 1 2 2 3 1 5 ``` ### 输出 #1 ```text 10011 ``` ## 说明/提示 在样例中，去 Korkeasaari 的孩子人数可以是 $1$，$4$ 或 $5$。 ### 数据规模与约定 - $1 \le n \le 10^5$ - $0 \le m \le 10^5$ - $1 \le a, b \le n$