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

Xem PDF



Tác giả:
Dạng bài
Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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 nhau. 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, và 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 \(n\)\(m\): 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 \(a\)\(b\): 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 và ngược lại (chuỗi nhị phân được đánh số từ \(1\)).

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

  • Giải thích: Số trẻ em có thể đi cùng nhau đến Korkeasaari là \(1\), \(4\), hoặc \(5\).

Bình luận


  • 0
    Thanh72 3:43 p.m. 19 Tháng 8, 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