Problem:


Problem B: Yu-kun Likes Letters in the English Alphabet

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらい英小文字が大好きだ。
そんなゆう君は紙と丸と線、そして英小文字を使う新しい遊びを考え、その採点用プログラムを書くことにした。

Problem

初期状態として、紙に V 個の丸と E 本の線が書かれている。丸には0から昇順に番号がつけられており、各丸の中には英小文字が1つ書かれているか、何も書かれていない。 各線は異なる２つの丸を結んでいる。1つの丸が26本以上の線で結ばれることはない。

遊びの手順は以下の通りである。

何も書かれていない丸を１つ選ぶ。 そのような丸が存在しない場合はこの処理を終了する。

丸の中に英小文字を１つ書く。　ただし丸が既に英小文字の書かれている丸と線で結ばれている場合、その英小文字と同じ英小文字は書くことはできない。

1. に戻る。

上記の手順に従って全ての丸に英小文字を書いた後、丸の番号が小さい順に丸の中の英小文字を並べ文字列を作る。
こうしてできる文字列を辞書順で最小となるようにしたい。
２つの同じ長さの文字列 s, t があり、 s が t より辞書順で小さいとは次のような場合を言う。
si は文字列 s の i 番目の英小文字を、 ti は文字列 t の i 番目の英小文字を表す。
si が ti と異なるような最小の i について、 si が ti より小さい。

紙の初期状態が与えられるので、そこから上記の手順にしたがって作成できる文字列のうち辞書順最小のものを出力せよ。

Input

V E
a0 a1 ... a(V-1)
s0 t0
s1 t1
...
s(E-1) t(E-1)

１行目に丸の数 V と線の数 E が空白区切りで与えられる。

２行目に丸の初期状態が空白区切りで与えられる。

ai が英小文字の場合は i 番目の丸にその英小文字が書かれており、'?'の場合は i 番目の丸には何も書かれていないことを表す。

続く E 行に線の情報がsi ti として与えられ、これはsi番の丸と ti 番の丸が線で結ばれていることを表す。

Constraints

入力は以下の条件を満たす。

1 ≤ V ≤ 100,000

0 ≤ E ≤ 200,000

ai は英小文字, または '?' のいずれか ( 0 ≤ i ≤ V-1 ) 

0 ≤ si, ti ≤ V-1 ( si < ti , 0 ≤ i ≤ E-1 ) 

１つの丸が26本以上の線で結ばれることはない

Output

問題文中の手順に従って作成可能な文字列のうち、辞書順で最も小さいものを1行に出力せよ

Sample Input 1

3 3
c ? ?
0 1
0 2
1 2

Sample Output 1

cab

Sample Input 2

3 2
c ? ?
0 1
0 2

Sample Output 2

caa

Sample Input 3

7 6
? a ? ? z a ?
0 1
0 2
3 4
4 5
4 6
5 6

Sample Output 3

baaazab

Sample Input 4

5 0
? ? ? ? ?

Sample Output 4

aaaaa



Sample input:
3 3
c ? ?
0 1
0 2
1 2


Sample output:
cab

Submission status: Accepted

Solution code:
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

v, e = map(int, input().split())
a = list(input().split())

g = [[] for _ in range(v)]
for _ in range(e):
    s, t = map(int, input().split())
    g[s].append(t)
    g[t].append(s)

for i in range(v):
    if a[i] != '?':
        continue

    for c in alphabet:
        flag = True
        for to in g[i]:
            if a[to] == c:
                flag = False
                break
        
        if flag:
            a[i] = c
            break

print(''.join(a))

Submission status: Accepted

Solution code:
V_, E_ = map(int, input().split())
A = input().split()
E = [[] for _ in range(V_)]
Used = [[False]*26 for _ in range(V_)]
for _ in range(E_):
    s, t = map(int, input().split())
    As, At = A[s], A[t]
    if As != "?":
        Used[t][ord(As)-97] = True
    if At != "?":
        Used[s][ord(At)-97] = True
    E[s].append(t)
    E[t].append(s)

for i, a in enumerate(A):
    if a == "?":
        for j in range(26):
            if not Used[i][j]:
                A[i] = chr(j + 97)
                for u in E[i]:
                    Used[u][j] = True
                break

print("".join(A))

Submission status: Accepted

Solution code:
v, e = map(int, input().split())
a_lst = input().split()
edges = [[] for _ in range(v)]
for _ in range(e):
    s, t = map(int, input().split())
    edges[s].append(t)
    edges[t].append(s)

for i in range(v):
    if "a" <= a_lst[i] <= "z": continue
    lst = {i for i in range(26)}
    for fr in edges[i]:
        lst.discard(ord(a_lst[fr]) - ord("a"))
    a_lst[i] = chr(min(lst) + ord("a"))

print("".join(a_lst))