Bạn muốn \(F\) người bạn của mình chia sẻ tin tức. Bạn biết rõ ai có thể nói chuyện với ai. Có \(P\) quan hệ một chiều, mỗi quan hệ là một cặp có thứ tự \((A_i,B_i)\), nghĩa là người bạn \(A_i\) có thể nói chuyện với người bạn \(B_i\). Điều này không có nghĩa \(B_i\) có thể nói chuyện với \(A_i\), mặc dù một cặp có thứ tự khác có thể cho phép chiều ngược lại.

Với mọi cặp có thứ tự \((A_i,B_i)\) hiện có, bạn muốn \(A_i\) chuyển một tin cho \(B_i\). Mỗi tin được biểu diễn bằng một số nguyên: giá trị tuyệt đối cho biết mức độ của tin, còn dấu cho biết đó là tin tốt hay tin xấu. Số nguyên này không được bằng \(0\) (nếu không thì chẳng có tin gì), và giá trị tuyệt đối không được lớn hơn \(F^2\) (nếu không thì tin quá sức kích động). Các quan hệ khác nhau có thể mang các giá trị khác nhau.

Vì quan tâm đến cảm xúc của bạn bè, với mỗi người, tổng giá trị của tất cả tin do người đó gửi phải bằng tổng giá trị của tất cả tin người đó nhận. Nếu một người không gửi tin nào thì tổng thứ nhất được coi là \(0\); nếu người đó không nhận tin nào thì tổng thứ hai cũng được coi là \(0\).

Hãy tìm một bộ giá trị tin thỏa tất cả các quy tắc trên, hoặc xác định rằng điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(F\) và \(P\): số người bạn và số cặp có thứ tự khác nhau. Tiếp theo là \(P\) dòng; dòng thứ \(i\) chứa hai số nguyên khác nhau \(A_i\) và \(B_i\), biểu thị rằng \(A_i\) có thể nói chuyện với \(B_i\). Các người bạn được đánh số từ \(1\) đến \(F\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\).

Nếu không có cách gán thỏa mãn, y là IMPOSSIBLE. Nếu có, y gồm \(P\) số nguyên khác \(0\), mỗi số thuộc đoạn \([-F^2,F^2]\). Số thứ \(i\) ứng với cặp có thứ tự thứ \(i\) trong dữ liệu vào và là giá trị tin mà người thứ nhất gửi cho người thứ hai. Toàn bộ các giá trị phải thỏa điều kiện cân bằng trong đề bài.

Nếu có nhiều đáp án, có thể in bất kỳ đáp án hợp lệ nào.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A_i\le F\) và \(1\le B_i\le F\) với mọi \(i\).
• \(A_i\ne B_i\) với mọi \(i\); một người không tự gửi tin cho chính mình.
• \((A_i,B_i)\ne(A_j,B_j)\) với mọi \(i\ne j\); không cặp có hướng nào bị lặp trong cùng một bộ test.

Phân nhóm

Test Set 1 (Visible): \(2\le F\le4\) và \(1\le P\le12\).

Test Set 2 (Hidden): \(2\le F\le1000\) và \(1\le P\le2000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
2 2
1 2
2 1
2 1
1 2
4 3
1 2
2 3
3 1
3 4
1 2
2 3
3 1
2 1
3 3
1 3
2 3
1 2

Case #1: 1 1
Case #2: IMPOSSIBLE
Case #3: -1 -1 -1
Case #4: 4 -4 -4 8
Case #5: -1 1 1

Nguồn

Google Code Jam 2017, Vòng 3, bài Good News and Bad News.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.