Authors have come up with the string $s$ consisting of $n$ lowercase Latin letters.

You are given two permutations of its indices (not necessary equal) $p$ and $q$ (both of length $n$). Recall that the permutation is the array of length $n$ which contains each integer from $1$ to $n$ exactly once.

For all $i$ from $1$ to $n-1$ the following properties hold: $s[p_i] \le s[p_{i + 1}]$ and $s[q_i] \le s[q_{i + 1}]$. It means that if you will write down all characters of $s$ in order of permutation indices, the resulting string will be sorted in the non-decreasing order.

Your task is to restore any such string $s$ of length $n$ consisting of at least $k$ distinct lowercase Latin letters which suits the given permutations.

If there are multiple answers, you can print any of them.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 26$) — the length of the string and the number of distinct characters required.

The second line of the input contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct integers from $1$ to $n$) — the permutation $p$.

The third line of the input contains $n$ integers $q_1, q_2, \dots, q_n$ ($1 \le q_i \le n$, all $q_i$ are distinct integers from $1$ to $n$) — the permutation $q$.


-----Output-----

If it is impossible to find the suitable string, print "NO" on the first line.

Otherwise print "YES" on the first line and string $s$ on the second line. It should consist of $n$ lowercase Latin letters, contain at least $k$ distinct characters and suit the given permutations.

If there are multiple answers, you can print any of them.


-----Example-----
Input
3 2
1 2 3
1 3 2

Output
YES
abb

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

String algorithms

Implementation

Greedy algorithms

Spanning trees

Data structures
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
(n, k) = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
offs = ord('a')
ans = [chr(offs + k - 1)] * n
pmore = set()
qmore = set()
let = 0
for i in range(n):
	pi = p[i]
	qi = q[i]
	if qi in pmore:
		pmore.remove(qi)
	else:
		qmore.add(qi)
	if pi in qmore:
		qmore.remove(pi)
	else:
		pmore.add(pi)
	ans[pi - 1] = chr(let + offs)
	if len(pmore) + len(qmore) == 0:
		let += 1
		if let == k:
			break
if let == k:
	print('YES')
	print(''.join(ans))
else:
	print('NO')


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : list(map(int, rd().strip().split()))
lat = [chr(ord('a') + i) for i in range(26)]
(n, k) = rrd()
p = list(rrd())
q = list(rrd())
cnt = [0] * 200005
ct = 0
ans = ['a'] * n
now = 0
for i in range(n):
	if q[i] == p[i]:
		if ct == 0 and i:
			now += 1
			now = min(now, 25)
		ans[q[i] - 1] = lat[now]
	else:
		if ct == 0 and i:
			now += 1
			now = min(now, 25)
		cnt[q[i]] += 1
		cnt[p[i]] += 1
		if cnt[q[i]] == 2:
			ct -= 1
		else:
			ct += 1
		if cnt[p[i]] == 2:
			ct -= 1
		else:
			ct += 1
		ans[p[i] - 1] = lat[now]
		ans[q[i] - 1] = lat[now]
if now + 1 >= k:
	print('YES')
	print(''.join(ans))
else:
	print('NO')


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
sp = set()
sq = set()
chuj = 0
odp = [chr(96 + 26) for i in range(n)]
for i in range(n):
	odp[p[i] - 1] = chr(97 + chuj)
	if p[i] - 1 in sq:
		sq.remove(p[i] - 1)
	else:
		sp.add(p[i] - 1)
	if q[i] - 1 in sp:
		sp.remove(q[i] - 1)
	else:
		sq.add(q[i] - 1)
	if len(sp) + len(sq) == 0:
		chuj += 1
	if chuj == 26:
		break
if chuj < k:
	print('NO')
else:
	print('YES')
	print(''.join(odp))


from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(50000)
(n, k) = map(int, stdin.readline().split())
p = list(map(int, stdin.readline().split()))
q = list(map(int, stdin.readline().split()))
pos = [0 for i in range(n)]
for i in range(n):
	p[i] -= 1
	q[i] -= 1
	pos[p[i]] = i
delta = [0 for i in range(n + 1)]
for i in range(n - 1):
	x = pos[q[i]]
	y = pos[q[i + 1]]
	if x > y:
		delta[y] += 1
		delta[x] -= 1
for i in range(1, n):
	delta[i] += delta[i - 1]
scc = [0 for i in range(n)]
num = 0
for i in range(n):
	if i == 0 or delta[i - 1] == 0:
		num += 1
	scc[i] = num
if num < k:
	print('NO')
	exit(0)
s = ['a' for i in range(n)]
for i in range(n):
	x = min(26, scc[i])
	s[p[i]] = chr(96 + x)
stdout.write('YES\n')
stdout.write(''.join(s))


import sys
inp = [int(x) for x in sys.stdin.read().split()]
n = inp[0]
k = inp[1]
P = inp[2:n + 2]
Q = inp[n + 2:n + n + 2]
letters = 'abcdefghijklmnopqrstuvwxyz'
index = [0] * n
for i in range(n):
	P[i] -= 1
	Q[i] -= 1
	index[P[i]] = i
intervals = []
for i in range(n - 1):
	if index[Q[i]] > index[Q[i + 1]]:
		intervals.append((index[Q[i + 1]], index[Q[i]]))
intervals.sort()
color = [0] * n
cur_color = 0
interval_idx = 0
last = -1
for i in range(n):
	if last < i:
		cur_color += 1
	color[i] = cur_color
	while interval_idx < len(intervals) and intervals[interval_idx][0] == i:
		last = max(last, intervals[interval_idx][1])
		interval_idx += 1
if cur_color < k:
	print('NO')
else:
	ans = ['a'] * n
	for i in range(n):
		ans[P[i]] = letters[min(25, color[i] - 1)]
	print('YES')
	print(''.join(ans))


import sys
input = sys.stdin.readline
from operator import itemgetter
(N, K) = map(int, input().split())
inP = list(map(int, input().split()))
inQ = list(map(int, input().split()))
P = [None] * N
for (i, p) in enumerate(inP):
	P[p - 1] = i + 1
Q = [None] * N
for (i, q) in enumerate(inQ):
	Q[q - 1] = i + 1
NUM = []
for (i, (p, q)) in enumerate(zip(P, Q)):
	NUM.append((i, p, q))
graph = [-1] * (N + 1)
NUM.sort(key=itemgetter(2))
for i in range(N - 1):
	pre = NUM[i][1]
	fow = NUM[i + 1][1]
	graph[fow] = pre
NUM.sort(key=itemgetter(1))
Color = [-1] * (N + 1)
color = 0
MAX = 1
for (ind, p, q) in NUM:
	if Color[p] == -1 and p > MAX:
		color += 1
	tmp = p
	while tmp != -1 and Color[tmp] == -1:
		MAX = max(MAX, tmp)
		Color[tmp] = color
		tmp = graph[tmp]
if color >= K - 1:
	print('YES')
	ans = [None] * N
	for (ind, p, q) in NUM:
		c = Color[p]
		ans[ind] = chr(97 + min(c, 25))
	print(''.join(ans))
else:
	print('NO')


from collections import deque
import sys
input = sys.stdin.readline

def scc():
	for i in range(1, n + 1):
		if not visit[i]:
			dfs1(i)
	for i in range(len(t) - 1, -1, -1):
		if not ok[t[i]]:
			s.append([])
			bfs(t[i])
	return

def dfs1(u):
	st = [u]
	while st:
		i = st[-1]
		visit[i] = 1
		if now1[i] == len(G[i]):
			t.append(st.pop())
		else:
			j = G[i][now1[i]]
			if not visit[j]:
				st.append(j)
			now1[i] += 1
	return

def bfs(u):
	q = deque()
	q.append(u)
	s[-1].append(u)
	ok[u] = 1
	while q:
		i = q.popleft()
		for j in R[i]:
			if not ok[j]:
				q.append(j)
				s[-1].append(j)
				ok[j] = 1
	return
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
R = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(p0, p1) = (p[i], p[i + 1])
	(q0, q1) = (q[i], q[i + 1])
	G[p0].append(p1)
	G[q0].append(q1)
	R[p1].append(p0)
	R[q1].append(q0)
(visit, ok) = ([0] * (n + 1), [0] * (n + 1))
(now1, now2) = ([0] * (n + 1), [0] * (n + 1))
(s, t) = ([], [])
scc()
ans = 'YES' if len(s) >= k else 'NO'
print(ans)
if ans == 'YES':
	ans = ['?'] * n
	c = 0
	for s0 in s:
		for i in s0:
			ans[i - 1] = chr(97 + min(c, 25))
		c += 1
	print(''.join(ans))


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

def get(cur):
	if cur >= 97 + 25:
		return chr(97 + 25)
	return chr(cur)
pos = [0] * (n + 1)
for (i, x) in enumerate(q):
	pos[x] = i
seg = [0]
cnt = 0
max_ = -1
for (i, x) in enumerate(p):
	max_ = max(max_, pos[x])
	if i == max_:
		cnt += 1
		seg.append(i + 1)
if len(seg) - 1 < k:
	print('NO')
else:
	cur = 97
	S = []
	for (s, e) in zip(seg[:-1], seg[1:]):
		for i in range(s, e):
			S.append(cur)
		cur += 1
	print('YES')
	print(''.join([get(S[pos[x]]) for x in range(1, n + 1)]))


from sys import stdin

def input():
	return next(stdin)

def main():
	(n, k) = map(int, input().split())
	pp = [int(p) for p in input().split()]
	qq = [int(q) for q in input().split()]
	(k, result) = solve(k, n, pp, qq)
	if k == 0:
		print('YES')
		print(''.join(result))
	else:
		print('NO')

def solve(k, n, pp, qq):
	qi = [0] * (n + 1)
	for (i, q) in enumerate(qq, 1):
		qi[q] = i
	qmin = n + 1
	qmins = [0] * (n + 1)
	for p in reversed(pp):
		q = qi[p]
		if q < qmin:
			qmin = q
		qmins[p] = qmin
	result = [''] * (n + 1)
	maxq = 0
	c = ord('a') - 1
	for p in pp:
		if qmins[p] >= maxq and k > 0:
			c += 1
			k -= 1
		result[p] = chr(c)
		if qi[p] > maxq:
			maxq = qi[p]
	return (k, result)
main()


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
s = list(map(int, input().split()))
d = [0] * (n + 5)
for q in range(n):
	d[s[q]] = q
(f, q2) = ([], 0)
for q in range(len(a)):
	if q - 1 == q2:
		f.append(q)
	q2 = max(q2, d[a[q]])
f.append(n)
if len(f) < k:
	print('NO')
else:
	print('YES')
	g = [chr(ord('a') + q) for q in range(30)]
	ans = ['' for q in range(n)]
	q1 = 0
	for q in range(n):
		if f[q1] == q:
			q1 += 1
			q1 = min(q1, 25)
		ans[a[q] - 1] = g[q1]
	print(''.join(ans))


(n, k) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
d = {}
j = 1
for i in l1:
	d[i] = j
	j += 1
l = [d[i] for i in l2]
wei = [0] * (n + 2)
right = [0] * (n + 2)
for i in range(n - 1):
	if l[i] < l[i + 1]:
		continue
	wei[l[i + 1]] += 1
	wei[l[i] + 1] -= 1
	right[l[i]] += 1
odcinki = []
l = 1
r = 1
pref = [0] * (n + 2)
for i in range(1, n + 2):
	pref[i] = pref[i - 1] + wei[i]
for i in range(1, n + 2):
	if pref[i] == 0:
		odcinki.append([l, r])
		l = i + 1
		r = i + 1
	elif pref[i] == right[i]:
		odcinki.append([l, r])
		l = i + 1
		r = i + 1
	else:
		r += 1
if odcinki[0] == [1, 1]:
	odcinki = odcinki[1:]
if odcinki[-1][0] == odcinki[-1][1] and odcinki[-1][0] > n:
	odcinki = odcinki[:-1]
lewe = [0] * (n + 1)
prawe = [0] * (n + 1)
for i in odcinki:
	lewe[i[0]] = 1
	prawe[i[1]] = 1
odp = [0] * (n + 3)
i = -1
indx = 1
reg = 0
odp = [-1] * (n + 3)
count = 0
while indx < n + 1:
	if prawe[indx - 1] == 1:
		reg = 0
	if lewe[indx] == 1:
		reg = 1
		count = 0
	odp[indx] = i
	if count == 0 or reg == 0:
		i += 1
	count += 1
	odp[indx] = i
	indx += 1
odpp = [0] * (n + 3)
for i in range(n):
	odpp[l1[i]] = odp[i + 1]
odpp = odpp[1:-2]
if max(odpp) + 1 < k:
	print('NO')
else:
	print('YES')
	for i in range(n):
		print(chr(97 + min(25, odpp[i])), end='')


(n, k) = map(int, input().split())
s = [0] * n
for (i, v) in enumerate(map(int, input().split())):
	s[v - 1] = i
t = [0] * n
for (i, v) in enumerate(map(int, input().split())):
	t[v - 1] = i
p = [0] * n
for (u, v) in zip(s, t):
	if u == v:
		continue
	elif v < u:
		(u, v) = (v, u)
	p[u] += 1
	p[v] -= 1
r = [0] * n
cur = 0
nxt = -1
for (i, v) in enumerate(p):
	if cur == 0 and nxt < 25:
		nxt += 1
	r[i] = nxt
	cur += v
if nxt < k - 1:
	print('NO')
else:
	print('YES')
	print(''.join(map(lambda x: chr(ord('a') + r[x]), s)))


from heapq import *

def solve(a, b):
	b_map = {i: idx for (idx, i) in enumerate(a)}
	intervals = []
	for (idx, i) in enumerate(b):
		f = b_map[i]
		intervals.append(sorted([f, idx]))
	intervals.sort(reverse=True)
	res = []
	endings = []
	for i in range(len(a)):
		while endings and endings[0] < i:
			heappop(endings)
		if not res:
			res.append(97)
		elif not endings:
			res.append(res[-1] + 1)
		else:
			res.append(res[-1])
		while intervals and intervals[-1][0] <= i:
			(s, e) = intervals.pop()
			heappush(endings, e)

	def build(k, r):
		res = [0] * len(k)
		for (idx, i) in enumerate(k):
			res[i - 1] = r[idx]
		return res
	return build(a, res)
(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
b = solve(a, b)
string = ''.join((chr(min(i, 97 + 25)) for i in b))
if len(set(string)) < k:
	print('NO')
else:
	print('YES')
	print(string)


import math
n = 3
k = 2
p = [1, 2, 3]
q = [1, 3, 2]
(n, k) = [int(x) for x in input().split(' ')]
p = [int(x) - 1 for x in input().split(' ')]
q = [int(x) - 1 for x in input().split(' ')]
group_ids = []
p_ids = set()
q_ids = set()
for i in range(n):
	if p[i] in q_ids:
		q_ids.remove(p[i])
	else:
		p_ids.add(p[i])
	if q[i] in p_ids:
		p_ids.remove(q[i])
	else:
		q_ids.add(q[i])
	if not bool(p_ids) and (not bool(q_ids)):
		group_ids.append(i)
if len(group_ids) < k:
	print('NO')
	return

def get_letter(_id):
	alphabet = 'abcdefghijklmnopqrstuvwxyz'
	return alphabet[min(_id, len(alphabet) - 1)]
print('YES')
result = [None] * n
l = 0
for i in range(len(group_ids)):
	r = group_ids[i]
	letter = get_letter(i)
	for it in range(l, r + 1):
		result[p[it]] = letter
	l = r + 1
print(''.join(result))


(n, k) = map(int, input().split())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
ab = 'abcdefghijklmnopqrstuvwxyz'
ss = {}
j = 0
it = []
for i in aa:
	ss[i] = j
	j += 1
jj = 0
for i in bb:
	ind = ss[i]
	(j, ind) = sorted([jj, ind])
	it.append([j, ind])
	jj += 1
it.sort()
do = 1
ma = it[0][1]
res = []
st = it[0][0]
for i in it[1:]:
	if i[0] <= ma:
		ma = max(ma, i[1])
	else:
		do += 1
		res.append([st, ma])
		st = i[0]
		ma = i[1]
	j += 1
if res == []:
	res = [[0, n - 1]]
elif res[-1][1] != n - 1:
	res.append([res[-1][1] + 1, n - 1])
if len(res) < k:
	print('NO')
else:
	print('YES')
	if len(res) > k:
		res = res[:k - 1] + [[res[k - 1][0], n - 1]]
	kk = -1
	res.sort()
	ll = [0] * n
	for i in res:
		kk += 1
		for j in range(i[0], i[1] + 1):
			ll[aa[j] - 1] = ab[kk]
	for i in ll:
		print(i, end='')
	print()


def main():
	(n, m) = list(map(int, input().split()))
	abc = list('zyxwvutsrqponmlkjihgfedcba'[26 - m:])
	res = [abc[0]] * (n + 1)
	(res[0], pool, f) = ('YES\n', [False] * (n + 1), 0)
	for (p, q) in zip(list(map(int, input().split())), list(map(int, input().split()))):
		if pool[p]:
			f -= 1
		else:
			pool[p] = True
			f += 1
		if pool[q]:
			f -= 1
		else:
			pool[q] = True
			f += 1
		res[p] = abc[-1]
		if not f:
			del abc[-1]
			if not abc:
				break
	print('NO' if abc else ''.join(res))

def __starting_point():
	main()
__starting_point()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

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

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
(n, k) = inpl()
p = inpl()
q = inpl()
se = set()
div = set()
ln = 0
for i in range(n):
	for x in [p[i], q[i]]:
		if x in se:
			se.discard(x)
			ln -= 1
		else:
			se.add(x)
			ln += 1
	if ln == 0:
		div.add(i)
if len(div) < k:
	print('NO')
else:
	res = [None] * n
	now = 0
	div = set(div)
	for i in range(n):
		res[p[i] - 1] = chr(97 + now)
		if i in div and now < 25:
			now += 1
	print('YES')
	print(''.join(res))


def process(P, Q, k):
	n = len(P)
	d = {}
	I = 0
	s = {}
	just_p = set([])
	just_q = set([])
	both = set([])
	for i in range(n):
		p = P[i]
		q = Q[i]
		if p == q:
			both.add(p)
		else:
			if q in just_p:
				just_p.remove(q)
				both.add(q)
			else:
				just_q.add(q)
			if p in just_q:
				just_q.remove(p)
				both.add(p)
			else:
				just_p.add(p)
		if len(just_p) == 0 and len(just_q) == 0:
			for x in both:
				d[x] = I
			I += 1
			both = set([])
	if I < k:
		return ['NO', '']
	answer = ['' for i in range(n)]
	for x in d:
		J = min(d[x], k - 1)
		answer[x - 1] = chr(ord('a') + J)
	answer = ''.join(answer)
	return ['YES', answer]
(n, k) = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
Q = [int(x) for x in input().split()]
(a1, a2) = process(P, Q, k)
print(a1)
if a1 == 'YES':
	print(a2)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
p = set()
q = set()
literals = ['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']
it = 0
s = [0] * n
for i in range(n):
	p.add(a[i])
	q.add(b[i])
	s[a[i] - 1] = literals[it]
	if a[i] in q:
		q.remove(a[i])
		p.remove(a[i])
	if b[i] in p:
		p.remove(b[i])
		q.remove(b[i])
	if not p and (not q):
		it = min(it + 1, 25)
		k -= 1
if k <= 0:
	arr = ''
	print('YES')
	for item in s:
		arr += item
	print(arr)
else:
	print('NO')


import sys

def main():
	(n, m) = [int(x) for x in sys.stdin.readline().strip().split()]
	p = [int(x) for x in sys.stdin.readline().strip().split()]
	q = [int(x) for x in sys.stdin.readline().strip().split()]
	sp = set()
	hashp = 0
	sq = set()
	hashq = 0
	res = ['z' for _ in range(n)]
	x = 0
	for (c1, c2) in zip(p, q):
		sp.add(c1)
		hashp += c1 * c1
		sq.add(c2)
		hashq += c2 * c2
		if hashp == hashq and sp == sq:
			c = chr(ord('a') + x)
			x += 1
			for pos in sp:
				res[pos - 1] = c
			if x == m:
				print('YES')
				print(''.join(res))
				return
			sp.clear()
			hashp = 0
			sq.clear()
			hashq = 0
	print('NO')
main()