F. Unstable String Sort
data structures; dfs and similar; dsu; graphs; greedy; implementation; strings
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.
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\).
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.