405715: GYM102055 B Balance of the Force

A long time ago in a galaxy far, far away, there was a group of knights who mastered the ancient power - the Force. To bring order and balance to the universe, the Force is divided into two categories that conflict with each other: the Jedi, who acts on the light side of the Force through non-attachment and arbitration, and the Sith, who uses the dark side through fear and aggression.

There were $$$N$$$ knights who mastered the Force. Each knight could join either the light side or the dark side. When joining the light side, the knight possesses $$$L_i$$$ Force; when joining the dark side, the knight possesses $$$D_i$$$ Force.

To maintain order and balance of the universe, the knights wanted to make the Force difference between the most powerful knight and the weakest knight as small as possible. To make things even tougher, some knights did not get along well, and they refused to join on the same side.

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 20$$$). $$$T$$$ test cases follow.

For each test case, the first line contains two integers $$$N$$$ ($$$1 \le N \le 2 \times 10^5$$$) and $$$M$$$ ($$$0 \le M \le 2 \times 10^5$$$), where $$$N$$$ is the number of knights and $$$M$$$ is the number of knight pairs that didn't get along well.

The next $$$M$$$ lines each contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \neq y \le N$$$), describing knight $$$x$$$ and knight $$$y$$$ didn't get along well.

The following $$$N$$$ lines each contains two integers, $$$L_i$$$ and $$$D_i$$$ ($$$1 \le L_i, D_i \le 10^9$$$), representing the Force when the knight joined the light side and the dark side.

For each test case, output one line containing "Case x: y", where x is the test case number (starting from $$$1$$$) and y is the minimum difference between the strongest knight and weakest knight, or "IMPOSSIBLE" (quotes for clarify) if it's impossible for the knights to pick side without violating the given constraints.

3
3 1
1 2
1 2
3 4
5 6
4 3
1 2
2 3
1 3
1 2
3 4
5 6
7 8
2 0
2 1
3 5

Case 1: 3
Case 2: IMPOSSIBLE
Case 3: 1

For the case 1, let knight 1 join the dark side then let knight 2 and 3 join the light side, the power of each knight are 2, 3 and 5, and the answer should be $$$5 - 2 = 3$$$.

For the case 3, let both knights join the light side, the answer becomes $$$3 - 2 = 1$$$.