CSES - School Excursion | Chuyến dã ngoại trường

View as PDF



Author:
Problem types
Points: 1800 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

A group of \(n\) children are coming to Helsinki. There are two possible attractions: a child can visit either Korkeasaari (zoo) or Linnanmäki (amusement park).

There are \(m\) pairs of children who want to visit the same attraction. Your task is to find all possible alternatives for the number of children that will visit Korkeasaari. The children's wishes have to be taken into account.

Input

  • The first input line has two integers \(n\) and \(m\): the number of children and their wishes. The children are numbered \(1,2,…,n\).
  • After this, there are \(m\) lines describing the children's wishes. Each line has two integers \(a\) and \(b\): children \(a\) and \(b\) want to visit the same attraction.

Output

  • Print a bit string of length \(n\) where a one-bit at index \(i\) indicates that it is possible that exactly \(i\) children visit Korkeasaari (the bit string is to be considered one-indexed).

Constraints

  • \(1\leq n \leq 10^5\)
  • \(1\leq m \leq 10^5\)
  • \(1\leq a, b \leq n\)

Example

Sample input

5 3  
1 2  
2 3  
1 5

Sample output

10011

Note

  • Explanation: The number of children visiting Korkeasaari can be \(1\), \(4\) or \(5\).

Comments


  • 0
    Thanh72    3:43 p.m. 19 aug, 2023

    Một nhóm \(n\) học sinh đang đến Helsinki. Có hai điểm tham quan: một học sinh có thể đến thăm Korkeasaari (sở thú) hoặc Linnanmäki (công viên giải trí).

    \(m\) cặp học sinh muốn đi tham quan cùng một địa điểm. Nhiệm vụ của bạn là tìm tất cả các cách lựa chọn số lượng học sinh tham quan Korkeasaari trong khi thỏa mãn mong muốn của các học sinh.

    Input

    • Dòng đầu tiên chứa hai số nguyên dương \(n\)\(m\) \((n, m \leq 10^5)\): số học sinh và mong muốn của chúng. Các học sinh được đánh số \(1, 2, ..., n\).
    • \(m\) dòng tiếp theo mô tả mong muốn của các học sinh. Mỗi dòng có hai số nguyên dương \(a\)\(b\) \((a, b \leq n)\): học sinh \(a\)\(b\) muốn đến thăm cùng một điểm tham quan.

    Output

    • In một chuỗi nhị phân có độ dài \(n\) trong đó bit thứ \(i\) có giá trị \(1\) khi có thể dẫn đúng \(i\) học sinh đến thăm Korkeasaari (Chuỗi nhị phân được đánh số từ \(1\)).

    Example

    Test 1

    Input
    5 3  
    1 2  
    2 3  
    1 5
    Output
    10011