Kiểm tra kế hoạch triển khai

Bối cảnh và bài toán

Một quy trình gồm n công việc và m quan hệ 'xong A mới được làm B'. Bộ phận vận hành chỉ cần biết liệu toàn bộ kế hoạch có thể hoàn tất hay không.

Yêu cầu

In POSSIBLE nếu tồn tại ít nhất một thứ tự hoàn thành mọi công việc, ngược lại in IMPOSSIBLE.

Input

Dòng đầu n, m; tiếp theo m cặp a, b.

Output

In "POSSIBLE" hoặc "IMPOSSIBLE".

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 2*10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 3
1 2
1 3
3 4

Output

POSSIBLE

Giải thích. Một thứ tự hoàn chỉnh tồn tại khi và chỉ khi đồ thị phụ thuộc là DAG.

Ví dụ 2

Input

2 2
1 2
2 1

Output

IMPOSSIBLE

Giải thích. Một thứ tự hoàn chỉnh tồn tại khi và chỉ khi đồ thị phụ thuộc là DAG.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.