codeforces 1213F

 1 #include<bits/stdc++.h>
 2 #define maxn 200005
 3 using namespace std;
 4 int n,k;
 5 int p[maxn],q[maxn];
 6 vector<int> g[maxn];
 7 stack<int> stk;
 8 vector<int> scc[maxn],g2[maxn];
 9 int pre[maxn],low[maxn],bel[maxn],Tim,cnt;
10 void tarjan(int u)
11 {
12     pre[u]=low[u]=++Tim;
13     stk.push(u);
14     for(int v:g[u])
15     {
16         if(!pre[v])tarjan(v),low[u]=min(low[u],low[v]);
17         else if(!bel[v])low[u]=min(low[u],pre[v]);
18     }
19     if(low[u]==pre[u])
20     {
21         cnt++;
22         while(1)
23         {
24             int x=stk.top();stk.pop();
25             bel[x]=cnt;
26             scc[cnt].push_back(x);
27             if(x==u)break;
28         } 
29     }
30 }
31 int dp[maxn];
32 void dfs(int u)
33 {
34     if(dp[u])return;
35     dp[u]=1;
36     for(int v:g2[u])
37     {
38         dfs(v);
39         dp[u]=max(dp[u],dp[v]+1);
40     }
41 }
42 char Ans[maxn];
43 int main()
44 {
45     scanf("%d%d",&n,&k);
46     for(int i=1;i<=n;++i)scanf("%d",&p[i]);
47     for(int i=1;i<=n;++i)scanf("%d",&q[i]);
48     for(int i=1;i<n;++i)g[p[i]].push_back(p[i+1]);
49     for(int i=1;i<n;++i)g[q[i]].push_back(q[i+1]);
50     cnt=0;Tim=0;
51     for(int i=1;i<=n;++i)if(!pre[i])tarjan(i);
52     for(int i=1;i<n;++i)
53     {
54         if(bel[p[i]]!=bel[p[i+1]])g2[bel[p[i]]].push_back(bel[p[i+1]]);
55         if(bel[q[i]]!=bel[q[i+1]])g2[bel[q[i]]].push_back(bel[q[i+1]]);
56     }
57     dfs(bel[p[1]]);
58     if(dp[bel[p[1]]]<k)puts("NO");
59     else
60     {
61         puts("YES");
62         for(int i=1;i<=cnt;++i)
63         {
64             int col=dp[i];
65             if(col>k)col=k;
66             for(int u:scc[i])Ans[u]=‘a‘+26-col;
67         }
68     }
69     printf("%s\n",Ans+1);
70 }