Get to Work (Small)

A company has its office in town $T$ and employs $E$ people. There are $N$ towns in the area, and every employee lives in one of them.

Some employees drive. Each employee comes with an integer $P$. If $P$ is $0$, that employee has no license and cannot drive. If $P$ is at least $1$, the car that employee drives holds $P$ people counting the driver, so $P = 1$ means the driver takes only themselves to work.

The only way an employee moves between towns is in an employee's car, and an employee rides only with a driver who lives in the same town. An employee who lives in town $T$ is already in the town with the office and needs no car.

Decide whether every employee can reach town $T$. If they can, choose the drivers so that the number of cars on the road is as small as possible, and find how many cars leave each town.

The first line contains the number of test cases $C$.

Each test case is given as follows.

• One line with the number of towns $N$ and the number $T$ of the town where the office is.
• One line with the number of employees $E$.
• $E$ lines describing one employee each. Each line has the number $H$ of the town that employee lives in and the capacity $P$ of the car that employee drives.

$1 \le C \le 50$, $1 \le N \le 10$, $1 \le T \le N$, $1 \le E \le 100$, $1 \le H \le N$, $0 \le P \le 6$.

Print one line per test case, in the order the test cases are given. Each line starts with Case #X: , where X is the number of the test case counting from $1$. After that print one of the following.

• IMPOSSIBLE, if there are not enough drivers for every employee to reach the office.
• If every employee can reach the office, print $N$ integers separated by one space, the number of cars leaving town $1$ through town $N$ when the total number of cars is minimal. The value for town $T$ is always $0$.