CSES - Even Outdegree Edges | Cạnh của đồ thị có đỉnh bậc ra là chẵn
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một đồ thị vô hướng, nhiệm vụ của bạn là định chiều mỗi cạnh để nhận được đồ thị có hướng thỏa mãn tất cả các đỉnh đều có bậc ra là chẵn. Bậc ra của một đỉnh là số lượng cung đi ra từ đỉnh đó.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) lần lượt là số đỉnh và số cạnh. Các đỉnh được đánh chỉ số từ \(1\) đến \(n\).
- \(m\) dòng tiếp theo mô tả danh sách cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) với ý nghĩa có một cạnh nối giữa đỉnh \(a\) và \(b\).
Đồ thị đã cho là một đơn đồ thị. Tức là giữa hai đỉnh bất kỳ chỉ có tối đa một cạnh nối giữa chúng và tất cả các cạnh đều nối giữa hai đỉnh phân biệt.
Output
- In ra \(m\) dòng mô tả chiều của các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) với ý nghĩa có một cung nối từ đỉnh \(a\) đến đỉnh \(b\). Bạn có thể in ra phương án bất kỳ. Nếu không tồn tại đáp án, in ra
IMPOSSIBLE.
Constraints
- \(1 \le n \le 10^5\)
- \(1 \le m \le 2 \times 10^5\)
- \(1 \le a, b \le n\)
Example
Sample input
4 4
1 2
2 3
3 4
1 4
Sample output
1 2
3 2
3 4
1 4
Bình luận
CSES - Even Outdegree Edges | Cạnh bậc ra chẵn
Bạn được cho một đồ thị vô hướng, nhiệm vụ của bạn là định chiều cho mỗi cạnh sao cho đồ thị mới có bậc ra của mọi đỉnh là chẵn. Bậc ra của một đỉnh được định nghĩa là số cung đi ra khỏi đỉnh đó.
Input
Đồ thị đã cho là đơn đồ thị. Tức giữa hai đỉnh bất kì có tối đa một cạnh nối giữa chúng và mọi cạnh đều nối hai đỉnh phân biệt.
Output
IMPOSSIBLE.Test 1
Input
Output