CSES - School Excursion | Chuyến dã ngoại trường
Xem PDF
Đ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í).
Có \(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\) và \(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\) và \(b\): học sinh \(a\) và \(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
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í).
Có \(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
Output
Example
Test 1
Input
Output