Keyence Programming Contest 2020 - Bichromization

We have a connected undirected graph with N vertices and M edges. Edge i in this graph (1 \leq i \leq M) connects Vertex U_i and Vertex V_i bidirectionally. We are additionally given N integers D_1, D_2, ..., D_N.

Determine whether the conditions below can be satisfied by assigning a color - white or black - to each vertex and an integer weight between 1 and 10^9 (inclusive) to each edge in this graph. If the answer is yes, find one such assignment of colors and integers, too.

* There is at least one vertex assigned white and at least one vertex assigned black.
* For each vertex v (1 \leq v \leq N), the following holds.
* The minimum cost to travel from Vertex v to a vertex whose color assigned is different from that of Vertex v by traversing the edges is equal to D_v.



Here, the cost of traversing the edges is the sum of the weights of the edges traversed.

Constraints

* 2 \leq N \leq 100,000
* 1 \leq M \leq 200,000
* 1 \leq D_i \leq 10^9
* 1 \leq U_i, V_i \leq N
* The given graph is connected and has no self-loops or multiple edges.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M
D_1 D_2 ... D_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M


Output

If there is no assignment satisfying the conditions, print a single line containing `-1`.

If such an assignment exists, print one such assignment in the following format:


S
C_1
C_2
\vdots
C_M


Here,

* the first line should contain the string S of length N. Its i-th character (1 \leq i \leq N) should be `W` if Vertex i is assigned white and `B` if it is assigned black.
* The (i + 1)-th line (1 \leq i \leq M) should contain the integer weight C_i assigned to Edge i.

Examples

Input

5 5
3 4 3 5 7
1 2
1 3
3 2
4 2
4 5


Output

BWWBB
4
3
1
5
2


Input

5 7
1 2 3 4 5
1 2
1 3
1 4
2 3
2 5
3 5
4 5


Output

-1


Input

4 6
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4


Output

BBBW
1
1
1
2
1
1

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
(N, M) = map(int, input().split())
D = list(map(int, input().split()))
dic2 = [[] for i in range(N)]
for i in range(M):
	(U, V) = map(int, input().split())
	U -= 1
	V -= 1
	if len(dic2[U]) == 0 or dic2[U][0][0] > D[V]:
		dic2[U] = []
		dic2[U].append([D[V], V, i])
	if len(dic2[V]) == 0 or dic2[V][0][0] > D[U]:
		dic2[V] = []
		dic2[V].append([D[U], U, i])
dic = [[] for i in range(N)]
for i in range(N):
	for j in dic2[i]:
		dic[i].append([j[1], j[2]])
end = [False] * N
color = [0] * N
q = []
ans = [10 ** 9] * M
for i in range(N):
	q.append([D[i], i])
q.sort()
for i in range(N):
	if end[q[i][1]]:
		continue
	flag = False
	for vi in dic[q[i][1]]:
		nexv = vi[0]
		mind = vi[1]
		nowd = q[i][0]
		nowp = q[i][1]
		if end[nexv]:
			flag = True
			color[nowp] = color[nexv] ^ 1
			end[nowp] = True
			ans[mind] = nowd
			break
		elif D[nexv] == nowd:
			flag = True
			color[nowp] = color[nexv] ^ 1
			end[nowp] = True
			end[nexv] = True
			ans[mind] = nowd
			break
		break
	if not flag:
		print(-1)
		sys.exit()
S = []
for i in color:
	if i == 0:
		S.append('B')
	else:
		S.append('W')
print(''.join(S))
print(' '.join(map(str, ans)))


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def impossible():
		for u in range(n):
			du = dd[u]
			for v in to[u]:
				if dd[v] <= du:
					break
			else:
				return True
		return False

	def dfs(u=0, pu=-1, c=0):
		color[u] = 'B' if c else 'W'
		for v in to2[u]:
			if v == pu:
				continue
			dfs(v, u, 1 - c)
	inf = 10 ** 9
	(n, m) = MI()
	dd = LI()
	to = defaultdict(list)
	uvtoi = {}
	for i in range(m):
		(u, v) = MI1()
		uvtoi[u, v] = uvtoi[v, u] = i
		to[u].append(v)
		to[v].append(u)
	if impossible():
		print(-1)
		exit()
	cost = [inf] * m
	to2 = defaultdict(set)
	for u in range(n):
		mn = (inf, inf, inf)
		for v in to[u]:
			t = (dd[v], uvtoi[u, v], v)
			if t < mn:
				mn = t
		v = mn[2]
		cost[mn[1]] = dd[u]
		to2[u].add(v)
		to2[v].add(u)
	color = ['N'] * n
	for u in range(n):
		if color[u] != 'N':
			continue
		dfs(u)
	print(''.join(color))
	print(*cost, sep='\n')
main()


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n

	def root(self, x):
		while self.parent[x] != x:
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def merge(self, x, y):
		(x, y) = (self.root(x), self.root(y))
		if x == y:
			return False
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.size[x] += self.size[y]
		self.parent[y] = x
		return True

	def issame(self, x, y):
		return self.root(x) == self.root(y)

	def getsize(self, x):
		return self.size[self.root(x)]
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read
(n, m) = [int(i) for i in readline().split()]
d = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
a = map(int, read().split())
for (i, (u, v)) in enumerate(zip(a, a)):
	u -= 1
	v -= 1
	g[u].append((v, i))
	g[v].append((u, i))
INF = 10 ** 9
ans = [INF] * m
UF = UnionFind(2 * n + 1)
dd = [(c, i) for (i, c) in enumerate(d)]
dd.sort()
for (c, idx) in dd:
	for (v, j) in g[idx]:
		if d[v] <= c:
			UF.merge(v, idx + n)
			UF.merge(v + n, idx)
			ans[j] = c
			break
	else:
		print(-1)
		exit()
s = []
T = 2 * n
for i in range(n):
	if UF.issame(T, i):
		s.append('W')
	elif UF.issame(T, i + n):
		s.append('B')
	else:
		s.append('W')
		UF.merge(T, i)
print(''.join(s))
print(*ans, sep='\n')


import sys
readline = sys.stdin.readline
from collections import Counter
(N, M) = map(int, readline().split())
D = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
Edgenum = Counter()
for i in range(M):
	(u, v) = map(int, readline().split())
	u -= 1
	v -= 1
	Edge[u].append((D[v], i, v))
	Edge[v].append((D[u], i, u))
	Edgenum[u, v] = i
	Edgenum[v, u] = i
inf = 10 ** 9 + 7
table = [inf] * M
Col = [None] * N

def solve():
	Di = sorted([(D[i], i) for i in range(N)])
	for (dvn, vn) in Di:
		(dvf, enum, vf) = min(Edge[vn])
		if dvn < dvf:
			return False
		table[enum] = dvn
	used = set()
	for i in range(N):
		if i in used:
			continue
		Col[i] = 1
		stack = [i]
		while stack:
			vn = stack.pop()
			for (_, enum, vf) in Edge[vn]:
				if table[enum] == inf:
					continue
				if vf in used:
					continue
				Col[vf] = not Col[vn]
				used.add(vf)
				stack.append(vf)
	for i in range(M):
		if table[i] == inf:
			table[i] = 10 ** 9
	return True
if not solve():
	print(-1)
else:
	print(''.join(['B' if Col[i] else 'W' for i in range(N)]))
	print('\n'.join(map(str, table)))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter
from collections import defaultdict
(N, M) = map(int, readline().split())
D = [0] + list(map(int, readline().split()))
m = map(int, read().split())
UV = list(zip(m, m))
graph = [[] for _ in range(N + 1)]
for (u, v) in UV:
	graph[u].append((v, D[v]))
	graph[v].append((u, D[u]))
subgraph = [[] for _ in range(N + 1)]
is_ng = False
for v in range(1, N + 1):
	graph[v].sort(key=itemgetter(1))
	(w, d) = graph[v][0]
	if D[v] < d:
		is_ng = True
		break
	subgraph[w].append(v)
if is_ng:
	print(-1)
	exit()
INF = 10 ** 9
wt_edge = defaultdict(lambda : INF)
color = [0] * (N + 1)
I = sorted(enumerate(D), key=itemgetter(1))[1:]
for (v, wt) in I:
	if color[v]:
		continue
	stack = [v]
	color[v] = 1
	v0 = v
	while stack:
		v = stack.pop()
		cw = 3 - color[v]
		for w in subgraph[v]:
			if w == v0:
				continue
			color[w] = cw
			wt_edge[v, w] = D[w]
			wt_edge[w, v] = D[w]
			stack.append(w)
S = ''.join(('B' if x == 1 else 'W' for x in color[1:]))
C = [wt_edge[u, v] for (u, v) in UV]
print(S)
print('\n'.join(map(str, C)))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
xs = list(map(int, input().split()))
G = [set() for _ in range(N + 1)]
es = []
for i in range(M):
	(u, v) = sorted(map(int, input().split()))
	if xs[u - 1] == xs[v - 1]:
		G[v].add(u)
		G[u].add(v)
	elif xs[u - 1] > xs[v - 1]:
		G[u].add(v)
	else:
		G[v].add(u)
	es.append((u, v))
(xs, d, cc) = (sorted([(x, i + 1) for (i, x) in enumerate(xs)]), {}, {})
for i in range(N):
	if not G[i + 1]:
		print(-1)
		sys.exit()
for (x, u) in xs:
	if u in cc:
		continue
	cc[u] = 1
	for c in G[u]:
		if c in cc:
			cc[u] = 1 - cc[c]
	S = [u]
	while S:
		q = S.pop()
		for c in G[q]:
			d[tuple(sorted([q, c]))] = x
			if c in cc:
				continue
			S.append(c)
			cc[c] = 1 - cc[q]
print(''.join(('BW'[cc[i]] for i in range(1, N + 1))))
for i in range(M):
	print(d[es[i]])


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
xs = list(map(int, input().split()))
G = [set() for _ in range(N)]
for i in range(M):
	(u, v) = sorted(map(int, input().split()), key=lambda x: [xs[x - 1], -x])
	G[v - 1].add((u - 1, i))
(xs, d, cc) = (sorted([(x, i) for (i, x) in enumerate(xs)]), [0] * M, [-1] * N)
for (x, u) in xs:
	if cc[u] + 1:
		continue
	if not G[u]:
		break
	cc[u] = 1
	for (c, _) in G[u]:
		if cc[c] + 1:
			cc[u] = 1 - cc[c]
	S = [u]
	while S:
		q = S.pop()
		for (c, i) in G[q]:
			d[i] = str(x)
			if cc[c] + 1:
				continue
			S.append(c)
			cc[c] = 1 - cc[q]
print(''.join(('BW'[i] for i in cc)) + '\n' + '\n'.join(d) if cc[u] + 1 else -1)


I = input
(N, M) = map(int, I().split())
(X, G, d, C) = (list(map(int, I().split())), [set() for _ in range(N)], [0] * M, [0] * N)
for i in range(M):
	(u, v) = sorted(map(int, I().split()), key=lambda x: [X[x - 1], -x])
	G[v - 1].add(u - 1)
	d[i] = str(X[v - 1])
for u in sorted(range(N), key=lambda i: X[i]):
	if C[u]:
		continue
	if not G[u]:
		break
	(C[u], S) = (-1 if sum((C[c] + 1 for c in G[u])) else 1, [u])
	while S:
		q = S.pop()
		for c in G[q]:
			if C[c]:
				continue
			S += [c]
			C[c] = -C[q]
print(''.join((' BW'[i] for i in C)) + '\n' + '\n'.join(d) if C[u] else -1)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
D = list(map(int, input().split()))
EDGE = [tuple(sorted(map(int, input().split()))) for i in range(M)]
DICE = dict()
for i in range(M):
	DICE[EDGE[i]] = i
E = [[] for i in range(N + 1)]
for (x, y) in EDGE:
	E[x].append(y)
	E[y].append(x)
P = [(x, ind + 1) for (ind, x) in enumerate(D)]
P.sort()
D = [0] + D
DECIDED = [''] * (N + 1)
DIS = [-1] * M
for (x, po) in P:
	flag = 0
	for to in E[po]:
		if DECIDED[to] != '':
			flag = 1
			break
	if flag == 0:
		for to in E[po]:
			if D[to] == x:
				DIS[DICE[tuple(sorted([po, to]))]] = x
				DECIDED[po] = 'B'
				DECIDED[to] = 'W'
				break
		else:
			print(-1)
			sys.exit()
	else:
		for to in E[po]:
			if DECIDED[to] != '' and DECIDED[po] == '':
				if DECIDED[to] == 'B':
					DECIDED[po] = 'W'
				else:
					DECIDED[po] = 'B'
				DIS[DICE[tuple(sorted([po, to]))]] = x
				break
			elif DECIDED[to] != '' and DECIDED[po] == DECIDED[to]:
				if x <= D[to]:
					continue
				DIS[DICE[tuple(sorted([po, to]))]] = x - D[to]
				break
			elif DECIDED[to] != '' and DECIDED[po] != DECIDED[to]:
				if x <= D[to]:
					continue
				DIS[DICE[tuple(sorted([po, to]))]] = x
				break
print(''.join(DECIDED[1:]))
for d in DIS:
	if d == -1:
		print(10 ** 9)
	else:
		print(d)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(2 * 10 ** 5)
(N, M) = map(int, input().split())
D = list(map(int, input().split()))
edge = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	edge[u - 1].append((v - 1, i))
	edge[v - 1].append((u - 1, i))
used = [False] * N
color = [-1 for i in range(N)]
C = [10 ** 9 for i in range(M)]
for v in range(N):
	if not used[v]:
		for (nv, id) in edge[v]:
			if D[nv] < D[v]:
				break
		else:
			for (nv, id) in edge[v]:
				if D[nv] == D[v]:
					C[id] = D[v]
					used[v] = True
					if not used[nv]:
						color[nv] = 0
						color[v] = 1
						used[nv] = True
					else:
						color[v] = 1 - color[nv]
					break
			else:
				exit(print(-1))
Edge = []
for v in range(N):
	if not used[v]:
		used[v] = True
		for (nv, id) in edge[v]:
			if D[nv] < D[v]:
				C[id] = D[v] - D[nv]
				Edge.append((v, nv, id))
				break
parent = [-1] * N
for (u, v, id) in Edge:
	parent[u] = v

def Coloring(v):
	if color[v] != -1:
		return color[v]
	else:
		color[v] = Coloring(parent[v])
		return color[v]
res = [''] * N
for i in range(N):
	if Coloring(i) == 0:
		res[i] = 'W'
	else:
		res[i] = 'B'
print(''.join(res))
for i in range(M):
	print(C[i])


from collections import defaultdict
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
bxs = list(map(int, input().split()))
xs = bxs[:]
dd = defaultdict(set)
for (i, x) in enumerate(xs):
	dd[x].add(i + 1)
xs = list(set(xs))
xs.sort()
G = [set() for _ in range(N + 1)]
G2 = [set() for _ in range(N + 1)]
es = []
for i in range(M):
	(u, v) = map(int, input().split())
	if bxs[u - 1] == bxs[v - 1]:
		G[v].add(u)
		G[u].add(v)
	elif bxs[u - 1] > bxs[v - 1]:
		G[u].add(v)
	else:
		G[v].add(u)
	e = (min(u, v), max(u, v))
	es.append(e)
r = True
d = dict()
cc = [-1 for _ in range(N + 1)]
for i in range(N):
	if len(G[i + 1]) == 0:
		print(-1)
		sys.exit()
for x in xs:
	for u in dd[x]:
		if cc[u] != -1:
			continue
		for c in G[u]:
			if cc[c] == -1:
				cc[u] = 1
				break
			else:
				cc[u] = 1 - cc[c]
		stack = [u]
		while stack:
			q = stack.pop()
			for c in G[q]:
				e = (min(q, c), max(q, c))
				if e in d:
					continue
				d[e] = x
				if cc[c] != -1:
					continue
				stack.append(c)
				cc[c] = 1 - cc[q]
for i in range(1, N + 1):
	if cc[i] == -1:
		print(-1)
		sys.exit()
for i in range(1, N + 1):
	print('B' if cc[i] else 'W', end='')
print()
for i in range(M):
	print(d[es[i]])


import sys
input = sys.stdin.readline
INF = 10 ** 9
(n, m) = map(int, input().split())
costs = [int(item) for item in input().split()]
costs_sorted = sorted([(item, i) for (i, item) in enumerate(costs)], reverse=True)
edge = [[] for _ in range(n)]
edge_dict = dict()
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	edge[u].append(v)
	edge[v].append(u)
	if u > v:
		(u, v) = (v, u)
	edge_dict[u, v] = i
visited = [0] * n
color = [-1] * n
costs_on_edge = [INF] * m
while costs_sorted:
	(c, v) = costs_sorted.pop()
	if visited[v]:
		continue
	visited[v] = True
	ok = False
	for nv in edge[v]:
		if costs[nv] <= c:
			if color[nv] == -1 and color[v] == -1:
				color[nv] = True
				color[v] = False
				visited[nv] = True
			else:
				color[v] = not color[nv]
			if nv < v:
				costs_on_edge[edge_dict[nv, v]] = c
			else:
				costs_on_edge[edge_dict[v, nv]] = c
			ok = True
			break
	if not ok:
		print(-1)
		exit()
color_str = ''
for item in color:
	if item == 1:
		color_str += 'W'
	else:
		color_str += 'B'
print(color_str)
for item in costs_on_edge:
	print(item)


import sys
input = sys.stdin.readline
(N, M) = list(map(int, input().split()))
D = list(map(int, input().split()))
UB = [list(map(int, input().split())) for _ in range(M)]
LL = [[-1] * 2 for _ in range(N)]
for i in range(M):
	(a, b) = UB[i]
	a -= 1
	b -= 1
	if D[a] < D[b]:
		LL[b] = [a, i]
	elif D[a] > D[b]:
		LL[a] = [b, i]
	else:
		LL[a] = [b, i]
		LL[b] = [a, i]
DD = [[0] * 2 for _ in range(N)]
for i in range(N):
	DD[i][0] = D[i]
	DD[i][1] = i
DD.sort()
L = [0] * N
H = [0] * M
for i in range(N):
	(h, x) = DD[i]
	if L[x] == 0:
		if LL[x][0] == -1:
			print(-1)
			exit()
		else:
			(n, m) = LL[x]
			H[m] = h
			if L[n] == 1:
				L[n] = 1
				L[x] = 2
			else:
				L[n] = 2
				L[x] = 1
for i in range(N):
	if L[i] == 1:
		L[i] = 'B'
	else:
		L[i] = 'W'
print(''.join(list(map(str, L))))
for i in range(M):
	if H[i] == 0:
		print(10 ** 9)
	else:
		print(H[i])


from collections import defaultdict
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
xs = list(map(int, input().split()))
dd = defaultdict(set)
for (i, x) in enumerate(xs):
	dd[x].add(i + 1)
G = [set() for _ in range(N + 1)]
G2 = [set() for _ in range(N + 1)]
es = []
for i in range(M):
	(u, v) = map(int, input().split())
	if xs[u - 1] == xs[v - 1]:
		G2[v].add(u)
		G2[u].add(v)
	elif xs[u - 1] > xs[v - 1]:
		G[u].add(v)
	else:
		G[v].add(u)
	e = (min(u, v), max(u, v))
	es.append(e)
xs = list(set(xs))
xs.sort()
d = dict()
cc = dict()
for i in range(N):
	if not (G[i + 1] or G2[i + 1]):
		print(-1)
		sys.exit()
for x in xs:
	for u in dd[x]:
		if u in cc or not G2[u]:
			continue
		cc[u] = 1
		stack = [u]
		while stack:
			q = stack.pop()
			for c in G2[q]:
				e = (min(q, c), max(q, c))
				d[e] = x
				if c in cc:
					continue
				stack.append(c)
				cc[c] = 1 - cc[q]
for x in xs:
	for i in dd[x]:
		for c in G[i]:
			e = (min(i, c), max(i, c))
			d[e] = x
			if i not in cc:
				cc[i] = 1 - cc[c]
print(''.join(('BW'[cc[i]] for i in range(1, N + 1))))
for i in range(M):
	print(d[es[i]])


class Union:

	def __init__(self, num):
		self.T = [-1 for i in range(num)]

	def root(self, x):
		if self.T[x] < 0:
			return x
		return self.root(self.T[x])

	def size(self, x):
		return -self.T[self.root(x)]

	def merge(self, x, y):
		a = self.root(x)
		b = self.root(y)
		if a == b:
			return False
		if self.size(a) < self.size(b):
			(a, b) = (b, a)
		self.T[a] += self.T[b]
		self.T[b] = a
		return True
(N, M) = list(map(int, input().split()))
D = list(map(int, input().split()))
UB = [list(map(int, input().split())) for _ in range(M)]
R = {}
for i in range(M):
	(a, b) = UB[i]
	a -= 1
	b -= 1
	if a not in R:
		R[a] = [[b, i]]
	else:
		R[a].append([b, i])
	if b not in R:
		R[b] = [[a, i]]
	else:
		R[b].append([a, i])
DD = [[0] * 2 for _ in range(N)]
for i in range(N):
	DD[i][0] = D[i]
	DD[i][1] = i
DD.sort()
L = [0] * N
H = [0] * M
for i in range(N):
	(h, x) = DD[i]
	if L[x] == 0:
		for (n, m) in R[x]:
			if D[n] == D[x] or L[n] != 0:
				H[m] = h
				if L[n] == 1:
					L[n] = 1
					L[x] = 2
				else:
					L[n] = 2
					L[x] = 1
				break
		else:
			print(-1)
			exit()
for i in range(N):
	if L[i] == 1:
		L[i] = 'B'
	else:
		L[i] = 'W'
print(''.join(list(map(str, L))))
for i in range(M):
	if H[i] == 0:
		print(10 ** 9)
	else:
		print(H[i])


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(n, m) = map(int, readline().split())
d = [-1]
d += list(map(int, readline().split()))
uv = list(map(int, read().split()))
inf = 10 ** 9
bw = ['?'] * (n + 1)
edge_cost = [inf] * (m + 1)
links = [dict() for _ in range(n + 1)]
links_same = [[-1, -1] for _ in range(n + 1)]
roots = set()
for i in range(1, m + 1):
	(u, v) = uv[(i - 1) * 2:i * 2]
	if d[u] == d[v]:
		links_same[u] = [v, i]
		links_same[v] = [u, i]
		roots.add(u)
		roots.add(v)
	elif d[u] < d[v]:
		links[u][v] = i
	else:
		links[v][u] = i
for root in roots:
	if bw[root] != '?':
		continue
	stack = [root]
	root2 = links_same[root][0]
	if bw[root2] == 'B':
		bw[root] = 'W'
	elif bw[root2] == 'W':
		bw[root] = 'B'
	else:
		bw[root] = 'B'
		bw[root2] = 'W'
		stack.append(root2)
	edge_cost[links_same[root][1]] = d[root]
	while stack:
		i = stack.pop()
		for (j, e) in links[i].items():
			if bw[j] != '?':
				continue
			bw[j] = bw[i]
			edge_cost[e] = d[j] - d[i]
			stack.append(j)
if bw.count('?') != 1:
	print(-1)
	exit()
print(''.join(bw[1:]))
print('\n'.join(map(str, edge_cost[1:])))


def main():
	import sys
	from collections import deque
	input = sys.stdin.readline

	class UnionFind:

		def __init__(self, n):
			self.n = n
			self.root = [-1] * (n + 1)
			self.rnk = [0] * (n + 1)

		def find_root(self, x):
			if self.root[x] < 0:
				return x
			else:
				self.root[x] = self.find_root(self.root[x])
				return self.root[x]

		def unite(self, x, y):
			x = self.find_root(x)
			y = self.find_root(y)
			if x == y:
				return
			elif self.rnk[x] > self.rnk[y]:
				self.root[x] += self.root[y]
				self.root[y] = x
			else:
				self.root[y] += self.root[x]
				self.root[x] = y
				if self.rnk[x] == self.rnk[y]:
					self.rnk[y] += 1

		def isSameGroup(self, x, y):
			return self.find_root(x) == self.find_root(y)

		def size(self, x):
			return -self.root[self.find_root(x)]
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	edge = []
	for _ in range(M):
		(u, v) = map(int, input().split())
		edge.append((u, v))
	e2i = {}
	for (i, e) in enumerate(edge):
		(u, v) = e
		e2i[u * (N + 1) + v] = i
	adj = [[] for _ in range(N + 1)]
	ok = [0] * (N + 1)
	ans = [0] * M
	edge.sort(key=lambda e: max(A[e[0] - 1], A[e[1] - 1]))
	UF = UnionFind(N + 1)
	adj = [[] for _ in range(N + 1)]
	for (u, v) in edge:
		if UF.isSameGroup(u, v):
			continue
		UF.unite(u, v)
		adj[u].append(v)
		adj[v].append(u)
		if A[u - 1] == A[v - 1]:
			ok[u] = 1
			ok[v] = 1
			ans[e2i[u * (N + 1) + v]] = A[u - 1]
		elif A[u - 1] < A[v - 1]:
			ok[v] = 1
			ans[e2i[u * (N + 1) + v]] = A[v - 1]
		else:
			ok[u] = 1
			ans[e2i[u * (N + 1) + v]] = A[u - 1]
	if sum(ok) != N:
		print(-1)
		exit()
	que = deque()
	que.append(1)
	seen = [0] * (N + 1)
	seen[1] = 1
	while que:
		v = que.popleft()
		for u in adj[v]:
			if seen[u] == 0:
				seen[u] = seen[v] * -1
				que.append(u)
	bw = ['B' if seen[i] == 1 else 'W' for i in range(1, N + 1)]
	print(''.join(bw))
	for a in ans:
		if a == 0:
			print(10 ** 9)
		else:
			print(a)
main()


import sys
(N, M) = map(int, input().split())
D = list(map(int, input().split()))
DI = list(zip(D, list(range(N))))
G = [[] for _ in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	G[u - 1].append((v - 1, i))
	G[v - 1].append((u - 1, i))
DI.sort()
V = [-1] * N
j = 0
used = [False] * N
ans = [10 ** 9] * M
BW = [''] * N
for j in range(N):
	(d, v) = DI[j]
	if used[v]:
		continue
	for (nv, i) in G[v]:
		if d == D[nv]:
			if BW[nv] == '':
				BW[nv] = 'B'
				BW[v] = 'W'
				ans[i] = d
				used[v] = True
				used[nv] = True
			elif BW[nv] == 'W':
				BW[v] = 'B'
				ans[i] = d
				used[v] = True
			else:
				BW[v] = 'W'
				ans[i] = d
				used[v] = True
			break
		elif used[nv]:
			if BW[nv] == 'B':
				BW[v] = 'B'
				ans[i] = d - D[nv]
				used[v] = True
			else:
				BW[v] = 'W'
				ans[i] = d - D[nv]
				used[v] = True
			break
	if not used[v]:
		print(-1)
		sys.exit()
print(*BW, sep='')
print(*ans, sep='\n')


import sys
from operator import itemgetter

def solve(n, m, ddd, links):
	ddi = list(enumerate(ddd))
	ddi.sort(key=itemgetter(1))
	LIMIT = 10 ** 9 + 1
	costs = [LIMIT] * m
	for (v, dv) in ddi:
		(du, li, u) = min(links[v])
		if du > dv:
			print(-1)
			return
		costs[li] = dv
	colors = [-1] * n
	for i in range(n):
		q = [(i, 0)]
		while q:
			(v, color) = q.pop()
			if colors[v] != -1:
				continue
			colors[v] = color
			for (du, li, u) in links[v]:
				if costs[li] == LIMIT:
					continue
				q.append((u, color ^ 1))
	MAX = 10 ** 9
	costs = [MAX if cost == LIMIT else cost for cost in costs]
	print(''.join(('BW'[c] for c in colors)))
	print('\n'.join(map(str, costs)))
(n, m) = map(int, input().split())
ddd = list(map(int, input().split()))
links = [[] for _ in range(n)]
for (li, line) in enumerate(sys.stdin):
	(u, v) = map(int, line.split())
	u -= 1
	v -= 1
	links[u].append((ddd[v], li, v))
	links[v].append((ddd[u], li, u))
solve(n, m, ddd, links)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

def argsort(li, key=None, reverse=False):
	return [i for (_, i) in sorted([(a, i) for (i, a) in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse)]
(N, M) = list(map(int, sys.stdin.buffer.readline().split()))
D = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N)]
for (i, (v, u)) in enumerate(VU):
	v -= 1
	u -= 1
	graph[v].append(u)
	graph[u].append(v)
edges = {}
colors = [None] * N
for v in argsort(D):
	d = D[v]
	if colors[v] is not None:
		continue
	for u in graph[v]:
		if colors[u] is not None:
			edges[v, u] = d
			colors[v] = not colors[u]
			break
		if D[u] == d:
			edges[v, u] = d
			colors[v] = True
			colors[u] = False
			break
	if colors[u] is None:
		print(-1)
		exit()
S = ''
for c in colors:
	S += 'B' if c else 'W'
ans = []
for (v, u) in VU:
	v -= 1
	u -= 1
	if (v, u) in edges:
		ans.append(edges[v, u])
	elif (u, v) in edges:
		ans.append(edges[u, v])
	else:
		ans.append(10 ** 9)
print(S)
print(*ans, sep='\n')