Trong một vương quốc xa xôi, có một hệ thống các thành phố và đường bộ kết nối giữa chúng. Mỗi thành phố được mô hình hóa như một đỉnh trong đồ thị, và mỗi tuyến đường hai chiều giữa hai thành phố là một cạnh vô hướng của đồ thị đó.

Nhà vua mong muốn có thể di chuyển từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác trong vương quốc, nhưng với điều kiện các tuyến đường phải có chiều hướng xác định, tức là mỗi tuyến đường chỉ cho phép di chuyển theo một hướng cố định. Để đảm bảo khả năng di chuyển này, hệ thống đường bộ cần phải được sắp xếp sao cho từ bất kỳ thành phố nào cũng có thể đến được tất cả các thành phố khác bằng cách đi theo các tuyến đường đã định chiều.

Nhiệm vụ của bạn là giúp nhà vua định chiều mỗi tuyến đường trong hệ thống sao cho toàn bộ đồ thị trở thành một đồ thị có hướng liên thông mạnh, nghĩa là từ bất kỳ thành phố nào cũng có thể đi đến mọi thành phố khác thông qua một hoặc nhiều tuyến đường có hướng.

Hãy xác định cách định chiều các tuyến đường để đáp ứng yêu cầu của nhà vua và đảm bảo sự liên thông mạnh mẽ trong toàn bộ hệ 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\).
• Đồ 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.

Dữ liệu ra

• In ra \(m\) số nguyên mô tả chiều của các cạnh. Số thứ \(i\) miêu tả chiều của cạnh thứ \(i\), \(-1\) nếu cạnh \(a,b\) ban đầu sẽ có chiều từ \(b\) đến \(a\), \(1\) nếu sẽ là chiều từ \(a\) đến \(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.

Ràng buộc

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

Input 1

3 3
1 2
1 3
2 3

Output 1

1 -1 1

Input 2

4 4
2 3
4 2
4 1
1 2

Output 2

IMPOSSIBLE