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