좋은 소식과 나쁜 소식 (작은 입력)

친구 $F$명 사이에 소식을 돌리려고 한다. 누가 누구에게 말을 걸 수 있는지는 이미 알고 있다. 한 방향 관계가 $P$개 있고, 각 관계는 순서쌍 $(A_i, B_i)$로 주어진다. 이는 친구 $A_i$가 친구 $B_i$에게 말을 걸 수 있다는 뜻이다. 친구 $B_i$가 친구 $A_i$에게 말을 걸 수 있다는 뜻은 아니다. 다만 다른 순서쌍이 그 관계를 따로 나타내기도 한다.

입력에 나온 모든 순서쌍 $(A_i, B_i)$마다 친구 $A_i$가 친구 $B_i$에게 소식을 하나씩 전한다. 소식은 정수 하나로 나타낸다. 절댓값은 소식의 크기이고, 부호는 소식의 종류, 즉 좋은 소식인지 나쁜 소식인지를 나타낸다. 이 정수는 0이 될 수 없고(0이면 전할 소식이 없다), 절댓값이 $F^2$보다 커질 수도 없다(그러면 소식이 너무 자극적이다). 순서쌍마다 값이 서로 달라도 된다.

친구들의 기분을 배려해서, 각 친구가 전하는 소식 값의 합과 그 친구가 받는 소식 값의 합이 같아야 한다. 전하는 소식이 하나도 없으면 그 합은 0이고, 받는 소식이 하나도 없으면 그 합도 0이다.

규칙을 모두 지키는 소식 값을 정할 수 있는지 판단하고, 정할 수 있으면 그 값을 구한다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 친구 수 $F$와 순서쌍 수 $P$가 공백으로 구분되어 주어진다. 이어지는 $P$개 줄 중 $i$번째 줄에는 서로 다른 두 정수 $A_i$와 $B_i$가 주어지고, 친구 $A_i$가 친구 $B_i$에게 말을 걸 수 있다는 뜻이다. 친구 번호는 1부터 $F$까지다.

제한

• $1 \le T \le 100$
• $2 \le F \le 4$
• $1 \le P \le 12$
• 모든 $i$에 대해 $1 \le A_i \le F$, $1 \le B_i \le F$, $A_i \ne B_i$ (자기 자신에게는 말을 걸지 않는다)
• $i \ne j$이면 $(A_i, B_i) \ne (A_j, B_j)$ (한 테스트 케이스 안에서 같은 순서쌍이 두 번 나오지 않는다)

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 규칙을 지키는 배정이 없으면 y는 IMPOSSIBLE이다. 배정이 있으면 y는 공백으로 구분한 정수 $P$개이고, $i$번째 정수는 입력의 $i$번째 순서쌍에 대응하며 그 순서쌍의 앞 친구가 뒤 친구에게 전하는 소식 값이다. 각 정수는 0이 아니어야 하고 $[-F^2, F^2]$ 안에 있어야 하며, 전체 값은 문제의 조건을 모두 만족해야 한다.

조건을 만족하는 배정이 여럿이면 사전순으로 가장 작은 하나만 출력한다. 수열 $(y_1, y_2, \dots, y_P)$를 정수 수열로 보고 앞에서부터 비교해 먼저 작은 값이 나오는 쪽이 더 작다. 예를 들어 $(-4, -4)$는 $(-4, -3)$보다 작고, $(-1, 5)$는 $(1, -5)$보다 작다.

• 소식을 받기만 하고 하나도 전하지 않는 친구가 있으면, 그 친구가 받는 값의 합은 0이 아닌데 전하는 값의 합은 0이므로 규칙을 지킬 수 없다.
• 소식을 전하지도 받지도 않는 친구가 있어도 규칙에는 어긋나지 않는다.
• 값을 모두 양수로 두어서는 풀리지 않는 입력이 있다. 이때는 음수 값을 써야 한다.
• 절댓값 상한은 친구 수에 따라 달라진다. 친구가 3명이면 $F^2 = 9$이므로 값 $-10$은 쓸 수 없다.