Cho một đồ thị vô hướng, nhiệm vụ của bạn là định chiều mỗi cạnh sao cho tạo thành được đồ thị có hướng không có chu trì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 phân biệt \(a\) và \(b\) với ý nghĩa có một cạnh nối giữa đỉnh \(a\) và \(b\).

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 bất kỳ đáp án nào thỏa mãn.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le m \le 2 \times 10^5\)
• \(1 \le a, b \le n\)

Example

Sample input

3 3
1 2
2 3
3 1

Sample output

1 2
3 2
3 1