Problem:
 Score : 900 points    Problem Statement 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 .         Sample Input 1 5 5
3 4 3 5 7
1 2
1 3
3 2
4 2
4 5      Sample Output 1 BWWBB
4
3
1
5
2  Assume that we assign the colors and integers as the sample output, and let us consider Vertex 5 , for example. To travel from Vertex 5 , which is assigned black, to a vertex that is assigned white with the minimum cost, we should make these moves: Vertex 5  \to Vertex 4  \to Vertex 2 . The total cost of these moves is 7 , which satisfies the condition. We can also verify that the condition is satisfied for other vertices.       Sample Input 2 5 7
1 2 3 4 5
1 2
1 3
1 4
2 3
2 5
3 5
4 5      Sample Output 2 -1       Sample Input 3 4 6
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4      Sample Output 3 BBBW
1
1
1
2
1
1

Solution (Python):
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])

Solution (Python):
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:])))

Solution (Python):

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)

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
D = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
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))

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)))

Solution (Python):
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)))

Solution (Python):
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)

Solution (Python):
import sys
I = sys.stdin.readline
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,i))
    d[i]=str(X[v-1])
for x, u in sorted((x,i)for i, x in enumerate(X)):
    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, i 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)

Solution (Python):
import sys
I = sys.stdin.readline
N, M = map(int, I().split())
X = list(map(int, I().split()))
G = [set() for _ in range(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,i))
X,d,C = sorted([(x,i) for i, x in enumerate(X)]),[0]*M,[0]*N
for x, u in X:
    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, i in G[q]:
            d[i]=str(x)
            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)

Solution (Python):
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)

Solution (Python):
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)]
for i in range(M):
    u, v = sorted(map(int, input().split()),key=lambda x:[xs[x-1],-x])
    G[v].add((u,i))
xs,d,cc = sorted([(x,i+1) for i, x in enumerate(xs)]),[0]*M,{}
for x, u in xs:
    if u in cc:
        continue
    if not G[u]:
        break
    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, i in G[q]:
            d[i] = str(x)
            if c not in cc:
                S.append(c)
                cc[c] = 1-cc[q]
print("".join("BW"[cc[i]] for i in range(1,N+1))+"\n"+"\n".join(d) if len(cc)==N else -1)

Solution (Python):
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()),key=lambda x:[xs[x-1],-x])
    G[v].add(u)
    es.append((v,u))
xs,d,cc = sorted([(x,i+1) for i, x in enumerate(xs)]),{},{}




for x, u in xs:
    if u in cc:
        continue
    if not G[u]:
        print(-1)
        sys.exit()
    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[(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]])

Solution (Python):
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]])

Solution (Python):
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 = 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)
    e = (min(u,v), max(u,v))
    es.append(e)

xs = sorted([(x,i+1) for i, x in enumerate(xs)])
d = dict()
cc = dict()
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]
    stack = [u]
    while stack:
        q = stack.pop()
        for c in G[q]:
            e = (min(q,c), max(q,c))
            d[e] = x
            if c in cc:
                continue
            stack.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]])

Solution (Python):
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]])

Solution (Python):
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]:
        G2[v].add(u)
        G2[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]) + len(G2[i+1]) == 0:
        print(-1)
        sys.exit()
for x in xs:
    for u in dd[x]:
        if cc[u] != -1:
            continue
        if 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))
                if e in d:
                    continue
                d[e] = x
                if cc[c] != -1:
                    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] = bxs[i-1]
            if cc[i] == -1:
                cc[i] = 1 - cc[c]
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]])

Solution (Python):
"""
明らかに無理→最小が2つ無い or 最小同士がペアになってない
(最小から接続する頂点に最小がない)

満たしてる→最小の辺を置いちゃおう
小さい奴からGreedyに置いてく？

自分の周りにendしてるやつ or 大きさが同じやつがあったら繋げちゃう
そのとき白黒はどうでも良さそう？

"""
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)))

Solution (Python):
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()

"""
コストが小さい順に、以下を行う
　コスト以下の点があれば、辺を結び、breakする
　なければアウト
"""
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")

Solution (Python):
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')

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

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)]








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())

INF = 10**9


for i,(u,v) in enumerate(zip(a,a)):
    u -= 1; v -= 1
    g[u].append((v,i))
    g[v].append((u,i))
    

ans = [INF]*m

dd = [(c,i) for i,c in enumerate(d)]
dd.sort()

UF = UnionFind(2*n)

def ng():
    print(-1)
    exit()

for c,idx in dd:
    conn = 0
    notconn = []
    for (v,i) in g[idx]:
        if d[v] <= c:
            UF.merge(v,idx+n)
            UF.merge(v+n,idx)
            ans[i] = c
            break
    else:
        ng()
                

s = []

good = set()
bad = set()
for i in range(n):
    p = UF.root(i)
    if p in bad:
        s.append("B")
    elif p in good:
        s.append("W")
    else:
        s.append("W")
        good.add(p)
        bad.add(UF.root(i+n))


print("".join(s))
    

print(*ans,sep="\n")

Solution (Python):
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)

Solution (Python):
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])