只考虑朋友关系之间相互移动太难做了。
正难则反，考虑不是朋友关系的一对位置，他们的相对位置一定不变。
这样就能构建出一个DAG，(每个点只连其前面一个和后面一个点，最多2N条边)
然后拓扑排序下 + 优先队列放置最小字典序的串即可！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
//#define m (l+r)/2
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e5+7;
const int N =1e4+7;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
string s;
map<string,int>mp,mm;
map<int,string>to;
int a[210][210];
int p[M],du[M],nxt[M][202];
int vs[M];//某个位置的字符是否固定
vector<int>pr,G[M];
struct node{int id,w;bool operator < (const node & r)const{if(w==r.w)return id>r.id;return w>r.w;}
};
int main()
{ios::sync_with_stdio(false);cin.tie(0);int S,L,n,sz=0;cin>>S>>L>>n;for(int i=1;i<=S;i++){cin>>s;mm[s]=i;} for(auto x:mm)mp[x.first]=++sz,to[sz]=x.first;for(int i=1;i<=L;i++){string u,v;cin>>u>>v;a[mp[u]][mp[v]]=a[mp[v]][mp[u]]=1;}
// cout<<"ok0"<<endl;priority_queue<node>q;for(int i=1;i<=n;i++){cin>>s;int w=mp[s];p[i]=w;}for(int i=n;i>=1;i--){for(int j=1;j<=S;j++)nxt[i][j]=nxt[i+1][j];int w = p[i];for(int j=1;j<=S;j++){if(!a[w][j]){if(nxt[i][j]!=0)du[nxt[i][j]]++,G[i].pb(nxt[i][j]);//cout<<" -=-=-=- "<<i<<" "<<j<<" "<<nxt[i][j]<<endl;}}nxt[i][p[i]]=i;}for(int i=1;i<=n;i++)if(du[i]==0)q.push(node{i,p[i]});//cout<<" = == = "<<i<<endl;;while(!q.empty()){node tp = q.top();q.pop();int x=tp.id,w=tp.w;pr.pb(w);// cout<<x<<" - "<<w<<endl;for(auto y:G[x]){du[y]--;if(du[y]==0)q.push(node{y,p[y]});}} for(auto x:pr){cout<<to[x]<<" ";}cout<<endl;return 0;
}