#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
int n,m;
struct nod
{
	int next,to;
}e[1000005];
int cnt;
int h[1000005];
void add(int x,int y)
{
	cnt++;
	e[cnt].next=h[x];
	h[x]=cnt;
	e[cnt].to=y;
}
ll dis[18][100005];
int vis[18][100005];
struct node
{
	ll x,dis;
	bool operator<(const node&w)const
	{
		return dis>w.dis;
	}
	node(){}
	node(int a,int b){x=a,dis=b;}
};
priority_queue<node>q;
int k;
int id[25];
void dij(int x)
{
	while(!q.empty())q.pop();
	dis[x][id[x]]=0;
	q.push(node(id[x],0));
	while(!q.empty())
	{
//	cout<<q.size()<<endl;
		int f=q.top().x;
		q.pop();
		if(vis[x][f])continue;
		vis[x][f]=1;
//		cout<<f<<endl;
		for(int i=h[f];i;i=e[i].next)
		{
			if(dis[x][e[i].to]>dis[x][f]+1)
			{
				dis[x][e[i].to]=dis[x][f]+1;
				if(!vis[x][e[i].to])q.push(node(e[i].to,dis[x][f]+1));
			}
		}
	}
}
ll s[25][25];
ll f[131078][18];//131072
signed main(){
	memset(dis,0x3f,sizeof(dis));
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
	{
		int a,b;
		a=read();
		b=read();
		add(a,b);
		add(b,a);
	}
	k=read();
	for(int i=1;i<=k;i++)id[i]=read();
	for(int i=1;i<=k;i++)dij(i);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			s[i][j]=dis[i][id[j]];
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=k;i++)f[(1<<i-1)][i]=0;
	for(int i=0;i<(1<<k);i++)
	{
		for(int j=1;j<=k;j++)
		{
			if(f[i][j]>1e9)continue;
			for(int t=1;t<=k;t++)
			{
				if(i&(1<<t-1))continue;
				f[i+(1<<t-1)][t]=min(f[i+(1<<t-1)][t],f[i][j]+s[j][t]);
			}
		}
	}
	ll ans=1e18;
	for(int j=1;j<=k;j++)
	{
		ans=min(ans,f[(1<<k)-1][j]);
	}
	if(ans>1e9)
	{
		puts("-1");
	}
	else cout<<ans+1<<endl;
	return 0;
}
#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define FORR(i, a, b) for(int i = (int)(a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
using VD = vector<double>;
using VII = vector<VI>;
using VLL = vector<VL>;
using VDD = vector<VD>;
using P = pair<int, int>;
using PL = pair<ll, ll>;

template <typename T>
bool chmax(T& a, const T& b) {
  if(a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
}

void solve(std::vector<std::string> S) {
  set<char> moji_set;
  vector<char> moji;
  REP(i, 3) {
    REP(j, S[i].size()) {
      if(moji_set.count(S[i][j]) > 0) continue;
      moji.push_back(S[i][j]);
      moji_set.insert(S[i][j]);
    }
  }
  sort(moji.begin(), moji.end());
  if(moji.size() > 10) {
    cout << "UNSOLVABLE" << endl;
    return;
  }
  if(moji.size() < 10) {
    char last = moji[moji.size() - 1];
    while(moji.size() != 10) {
      moji.push_back(last + 1);
      last++;
    }
  }
  do {
    map<char, int> moji_map;
    REP(i, moji.size()) {
      moji_map[moji[i]] = i;
    }
    VLL N_dash(3);
    bool num_ok = true;
    REP(i, 3) {
      REP(j, S[i].size()) {
        char tmp = S[i][j];
        if(j == 0 && moji_map[tmp] == 0) num_ok = false;
        N_dash[i].push_back(moji_map[tmp]);
      }
    }
    if(!num_ok) continue;
    VL N(3);
    REP(i, 3) {
      ll mul = 1;
      N[i] = 0;
      reverse(N_dash[i].begin(), N_dash[i].end());
      REP(j, N_dash[i].size()) {
        N[i] += N_dash[i][j] * mul;
        mul *= 10;
      }
    }
    if(N[0] + N[1] == N[2]) {
      REP(i, 3) {
        cout << N[i] << endl;
      }
      return;
    }
  } while(next_permutation(moji.begin(), moji.end()));
  cout << "UNSOLVABLE" << endl;
  return;
}

int main() {
  std::vector<std::string> S(3);
  for(int i = 0; i < 3; i++) {
    std::cin >> S[i];
  }
  solve(std::move(S));
  return 0;
}
