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

친구 $F$명에게 소식을 전하려고 한다. 누가 누구에게 말을 걸 수 있는지는 이미 알고 있다. 일방향 관계가 $P$개 있고, $i$번째 관계는 순서쌍 $(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$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다. 각 테스트 케이스의 첫 줄에는 친구의 수 $F$와 순서쌍의 수 $P$가 공백을 사이에 두고 주어진다. 이어지는 $P$개의 줄 중 $i$번째 줄에는 서로 다른 두 정수 $A_i$와 $B_i$가 주어지며, 친구 $A_i$가 친구 $B_i$에게 말을 걸 수 있다는 뜻이다. 친구는 1번부터 $F$번까지 번호가 붙어 있다.

제한

• $1 \le T \le 100$
• $2 \le F \le 1000$
• $1 \le P \le 2000$
• 모든 $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$는 다음 둘 중 하나다.

규칙을 지키는 배정이 없으면 $y$는 IMPOSSIBLE이다.

배정이 있으면 $y$는 공백 하나로 구분한 정수 $P$개이고, $i$번째 정수는 친구 $A_i$가 친구 $B_i$에게 전하는 소식 값이다. 규칙을 지키는 배정은 여러 가지이므로, 다음 절차가 만드는 배정을 그대로 출력한다.

1. 친구 1번부터 $F$번까지를 정점으로 삼고 $i$번째 간선이 $A_i$와 $B_i$를 잇는 무방향 다중 그래프를 만든다. 간선 번호는 입력 순서를 그대로 따른다.
2. 이 그래프를 깊이 우선 탐색한다. 아직 방문하지 않은 친구 중 번호가 가장 작은 친구에서 탐색을 시작하고, 모든 친구를 방문할 때까지 되풀이한다. 한 친구에서는 그 친구에 연결된 간선을 번호가 작은 것부터 살펴보되, 그 친구로 들어올 때 쓴 간선 하나는 건너뛴다. 아직 방문하지 않은 친구로 이어지는 간선은 탐색 숲의 트리 간선이 되고, 나머지 간선은 모두 어떤 친구와 그 친구의 조상을 잇는 역방향 간선이 된다.
3. 역방향 간선 $i$가 친구 $u$와 그 조상 $w$를 잇는다고 하자. 간선 $i$와 숲에서 $w$부터 $u$까지 내려가는 경로가 이루는 순환을 따라 소식 1단위를 보낸다. 이 1단위는 간선 $i$에서 $u$에서 $w$로 흐르고, 숲의 경로에서 $w$에서 $u$ 쪽으로 흐른다.
4. 역방향 간선을 모두 처리한 뒤, 간선 $i$의 값은 그 간선에 흐른 양의 합이다. 흐름이 $A_i$에서 $B_i$ 방향이면 양수로 세고, $B_i$에서 $A_i$ 방향이면 음수로 센다.

규칙을 지키는 배정이 있는 경우, 이 절차가 만드는 값은 항상 0이 아니고 $[-F^2, F^2]$ 안에 있다.

소식을 하나도 전하지 않고 받지도 않는 친구가 있어도 규칙은 지켜진다.

어떤 친구가 소식을 받기만 하고 아무에게도 전하지 못하면 그 테스트 케이스는 IMPOSSIBLE이다. 소식 값은 0이 될 수 없어서 받은 값의 합이 0이 아닌데, 전한 값의 합은 0이기 때문이다.

절댓값이 $F^2$을 넘는 값은 다른 규칙을 모두 지켜도 쓸 수 없다.

음수 값을 하나도 쓰지 않으면 풀리지 않는 경우도 있다.