会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらい英小文字が大好きだ。 そんなゆう君は紙と丸と線、そして英小文字を使う新しい遊びを考え、その採点用プログラムを書くことにした。
初期状態として、紙に V 個の丸と E 本の線が書かれている。丸には0から昇順に番号がつけられており、各丸の中には英小文字が1つ書かれているか、何も書かれていない。 各線は異なる2つの丸を結んでいる。1つの丸が26本以上の線で結ばれることはない。
遊びの手順は以下の通りである。
上記の手順に従って全ての丸に英小文字を書いた後、丸の番号が小さい順に丸の中の英小文字を並べ文字列を作る。 こうしてできる文字列を辞書順で最小となるようにしたい。 2つの同じ長さの文字列 s, t があり、 s が t より辞書順で小さいとは次のような場合を言う。 si は文字列 s の i 番目の英小文字を、 ti は文字列 t の i 番目の英小文字を表す。 si が ti と異なるような最小の i について、 si が ti より小さい。
紙の初期状態が与えられるので、そこから上記の手順にしたがって作成できる文字列のうち辞書順最小のものを出力せよ。
V E a0 a1 ... a(V-1) s0 t0 s1 t1 ... s(E-1) t(E-1)
1行目に丸の数 V と線の数 E が空白区切りで与えられる。
2行目に丸の初期状態が空白区切りで与えられる。
ai が英小文字の場合は i 番目の丸にその英小文字が書かれており、'?'の場合は i 番目の丸には何も書かれていないことを表す。
続く E 行に線の情報がsi ti として与えられ、これはsi番の丸と ti 番の丸が線で結ばれていることを表す。
入力は以下の条件を満たす。
問題文中の手順に従って作成可能な文字列のうち、辞書順で最も小さいものを1行に出力せよ
3 3 c ? ? 0 1 0 2 1 2
cab
3 2 c ? ? 0 1 0 2
caa
7 6 ? a ? ? z a ? 0 1 0 2 3 4 4 5 4 6 5 6
baaazab
5 0 ? ? ? ? ?
aaaaa