Đồ Thị Con Euler
Nộp bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Python 3
5.0s
Giới hạn bộ nhớ:
256M
Đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Go, Java, Kotlin, Pascal, Python, Scratch
Cho đồ thị vô hướng gồm nút và cạnh. Hãy đếm số đồ thị con (gồm tất cả các nút và một tập con các cạnh) sao cho mỗi nút có bậc chẵn.
In ra kết quả theo modulo .
Dữ liệu vào
- Dòng 1: hai số nguyên và .
- dòng tiếp theo: mỗi dòng gồm hai số nguyên và — cạnh nối nút và nút .
Dữ liệu ra
- Một số nguyên duy nhất — số đồ thị con Euler modulo .
Ràng buộc
- Mỗi cạnh nối hai nút phân biệt
- Không có hai cạnh cùng nối một cặp nút
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 3 1 2 1 3 2 3 |
2 | Hai đồ thị con hợp lệ: đồ thị rỗng (không cạnh nào) và đồ thị đầy đủ (cả 3 cạnh). Nút 4 bị cô lập nên bậc của nó luôn là 0 (chẵn). |
| 3 2 1 2 2 3 |
1 | Chỉ có đồ thị rỗng hợp lệ — không thể chọn cạnh nào mà vẫn giữ mọi bậc chẵn trên đường đi 1-2-3. |
Bình luận