CSES - Even Outdegree Edges | Cạnh của đồ thị có đỉnh bậc ra là chẵn

Xem PDF
Tác giả:
nhphucqt
Dạng bài
Đ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


  • -1
    nguyen_ducminh    10:55 p.m. 1 Tháng 9, 2023

    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

    • Dòng đầu tiên gồm hai số nguyên \(n\) (\(1 \leq n \leq 10^5\)) và \(m\) (\(1 \leq m \leq 2\times10^5\)) - số lượng đỉnh và cạnh. Các đỉnh được đánh chỉ số \(1,2,...,n\).
    • \(m\) dòng tiếp theo mô tả các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\) (\(1 \leq a,b \leq n\)) với ý nghĩa có cạnh nối giữa hai đỉnh \(a\) và \(b\).

    Đồ 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

    • Gồm \(m\) dòng mô tả chiều của các cung. Mỗi dòng gồm hai số nguyên \(a\) và \(b\) với ý nghĩa có cung nối từ đỉnh \(a\) tới đỉnh \(b\). Bạn có thể in ra một phương án hợp lệ bất kì.
    • Nếu không tồn tại phương án, in ra IMPOSSIBLE.

    Test 1

    Input 
    4 4
1 2
2 3
3 4
1 4
    Output 
    1 2
3 2
3 4
1 4