Trong một thế giới tương lai, một tập đoàn công nghệ hàng đầu đang phát triển một mạng lưới giao thông siêu tốc cho một thành phố thông minh. Mỗi nút giao thông trong thành phố được mô hình hóa dưới dạng một đỉnh trong đồ thị, và các tuyến đường tiềm năng giữa chúng được mô hình hóa dưới dạng các cạnh vô hướng.

Để tối ưu hóa cho hệ thống điều khiển giao thông và tránh các tình trạng tắc nghẽn hoặc xung đột, tập đoàn quyết định rằng tất cả các tuyến đường phải được định chiều theo một hướng duy nhất. Mục tiêu là đảm bảo rằng không có bất kỳ tuyến đường nào tạo ra vòng lặp, tức là không tồn tại chu trình nào trong hệ thống giao thông. Điều này sẽ giúp cho việc điều hướng và điều phối giao thông trở nên đơn giản và hiệu quả hơn, đồng thời đảm bảo mọi lộ trình trong thành phố đều có điểm bắt đầu và điểm kết thúc rõ ràng.

Nhiệm vụ của bạn là đề xuất cách định chiều cho mỗi tuyến đường trong mạng lưới sao cho toàn bộ hệ thống trở thành một đồ thị có hướng không có chu trình (DAG), đảm bảo tính lưu thông tối ưu và ngăn chặn tình trạng tắc nghẽn giao thông.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(n,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,b\) với ý nghĩa có một cạnh nối giữa hai đỉnh \(a,b\).

Dữ liệu ra

• 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.

Ràng buộc

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

Input 1

3 3
1 2
2 3
3 1

Output 1

1 2
3 2
3 1