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

문제

친구 $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$ 은 쓸 수 없다.