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 NN 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 LiL_i Force; when joining the dark side, the knight possesses DiD_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.

Input

The first line of the input gives the number of test cases, TT (1≤T≤20)(1≤T≤20). TT test cases follow.

For each test case, the first line contains two integers NN (1≤N≤2×105)(1≤N≤2×10^5) and MM (0≤M≤2×105)(0≤M≤2×10^5), where NN is the number of knights and MM is the number of knight pairs that didn’t get along well.

The next MM lines each contains two integers xx and yy (1≤x≠y≤N)(1≤x≠y≤N), describing knight xx and knight yy didn’t get along well.

The following NN lines each contains two integers, LiL_i and DiD_i (1≤Li,Di≤109)(1≤Li,Di≤10^9), representing the Force when the knight joined the light side and the dark side.

Output

For each test case, output one line containing “Case x: y”, where x is the test case number (starting from 11) 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.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

output

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

Note

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=35−2=3.

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

 

题意：有N个骑士，黑暗和光明两个派别，他们中有几对人互相厌恶，因此不能放在一派，每个人选择一派后会获得一定的能力值，要使得能力值最大的骑士与能力值最小的骑士的能力值差值最小。

刚开始看到差值最小，第一反应是二分答案，但在这题里虽然可以做，但写起来很烦，也不是最好的做法。

首先，存在矛盾关系，所以如果每个联通块不是二分图，则无解。

二分图染色，可以确定每个联通块的最大能力值，最小能力值，（有两对），用这两对（最大值，最小值）代表这个联通块。

则总共有2 * cnt_block个区间，现在要找到一个大区间，包含cnt_block个不同的小区间。

若直接枚举区间需要 n2n^2，但是直到大区间的左端点一定是某一个小区间的左端点，大区间的右端点一定是某个小区间的右端点，所以考虑按顺序枚举区间左端点，找到符合条件且最小的右端点。

从最大的小区间左端点开始枚举，向左枚举。

要从最大的开始，是因为如果从最小的开始，则不能确定当前大区间中有几个不同的小区间，而从最大的开始，则包含的区间一定是已经枚举过的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int T, n, m;
vector<int>G[maxn], block[maxn];
int color[maxn], force[maxn][2], mx[maxn], mn[maxn];
bool vis[maxn];
struct X
{
	int val, id;
};
vector<X>vc;
bool cmp(const X& a, const X&b) {
	return a.val > b.val;
}
void add_edge(int u, int v) {
	G[u].push_back(v);
	G[v].push_back(u);
}
bool dfs(int dfn, int u, int x) {
	if (color[u] != -1) {
		if (color[u] == x)return true;
		else return false;
	}
	color[u] = x;
	block[dfn].push_back(u);
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (!dfs(dfn, v, x ^ 1))return false;
	}
	return true;
}
multiset<int,greater<int> >st;
int main() {
	scanf("%d", &T);
	for (int tt = 1; tt <= T; tt++) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)G[i].clear();
		for (int i = 0; i <= n; i++)block[i].clear();
		vc.clear(); 
		st.clear();
		memset(mx, 0, sizeof(mx));
		memset(mn, 0x3f, sizeof(mn));
		memset(color, -1, sizeof(color));
		memset(vis, 0, sizeof(vis));
		for (int i = 0; i < m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			add_edge(u, v);
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &force[i][0], &force[i][1]);
		}
		bool flg = 1;
		int cnt_blo = 0;
		for (int i = 1; i <= n; i++) {
			if (color[i] == -1) {
				if (!dfs(cnt_blo, i, 0)) {
					flg = 0;
					break;
				}
				cnt_blo++;
			}
		}
		if (!flg) {
			printf("Case %d: IMPOSSIBLE\n", tt);
			continue;
		}
		for (int i = 0; i < cnt_blo; i++) {
			for (int v : block[i]) {
				mx[i << 1] = max(mx[i << 1], force[v][color[v]]);
				mn[i << 1] = min(mn[i << 1], force[v][color[v]]);
				mx[i << 1 | 1] = max(mx[i << 1 | 1], force[v][color[v] ^ 1]);
				mn[i << 1 | 1] = min(mn[i << 1 | 1], force[v][color[v] ^ 1]);
			}
			vc.push_back(X{ mn[i << 1],i << 1 });
			vc.push_back(X{ mn[i << 1 | 1],i << 1 | 1 });
		}
		int cnt_diff = 0, ans = INF;
		sort(vc.begin(), vc.end(), cmp);
		for (int i = 0; i < vc.size(); i++) {
			int now = vc[i].id;
			st.insert(mx[now]);
			vis[now] = true;
			if (vis[now ^ 1])st.erase(max(mx[now], mx[now ^ 1])), vis[now ^ 1] = false;
			else cnt_diff++;
			if (cnt_diff == cnt_blo)ans = min(ans, *st.begin() - mn[now]);
		}
		printf("Case %d: %d\n", tt, ans);
	}
	return 0;
}