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

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

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

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

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

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