Get to Work (Large)

A company in town $T$ has $E$ employees. The area holds $N$ towns where those employees live. Every employee has to reach town $T$, and you want as few cars on the road as possible.

The rules are these.

• The only way an employee travels between towns is in a car owned by an employee.
• An employee can only ride with an employee who lives in the same town.
• A driving employee drives a car with a capacity of $P$ people. The capacity counts the driver, so $P = 1$ means the driver can carry nobody else. $P = 0$ means the employee has no licence and cannot drive.
• The number of cars used has to be the smallest possible.

An employee who lives in town $T$ is already at the office and needs no car.

Decide whether every employee can get to work, and if so, how many cars leave each town for the office.

The first line holds an integer $C$, the number of test cases.

Each test case is given as follows.

• One line with the number of towns in the area $N$ and the number of the town where the office is, $T$, separated by a space.
• One line with the number of employees $E$.
• $E$ lines, one per employee. Each line holds the number of the town the employee lives in, $H$, and the capacity of the car that employee drives, $P$, separated by a space. If the employee has no licence, $P$ is $0$.

Limits

• $1 \le C \le 100$
• $1 \le N \le 100$
• $1 \le T \le N$
• $1 \le E \le 500$
• $1 \le H \le N$
• $0 \le P \le 6$

Print one line per test case, in the order the test cases appear in the input. Each line starts with the string Case #X: , where $X$ is the test case number counting from $1$. Follow it with one of these.

• The string IMPOSSIBLE, if there are not enough drivers for every employee to commute.
• Otherwise $N$ space separated integers, one for each town from $1$ to $N$, giving the number of cars that commute from that town.