#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <string>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <ctime>
#include <cassert>
#include <fstream>
#include <stack>
#include <random>
#include <iomanip>

#include <fstream>


using namespace std;
typedef long long ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

struct edge{ll to,cost; };
vector<edge> G[500010];
ll d[500010];

void dijkstra(ll s){
    fill(d,d+500010,inf);
    d[s]=0;
    priority_queue<l_l,vector<l_l>,greater<l_l>> que;
    que.push(l_l(0,s));
    while(!que.empty()){
        l_l p=que.top();que.pop();
        ll v=p.second;
        if(d[v]<p.first)continue;
        if(G[v].size()>0){
            rep(i,0,G[v].size()-1){
                edge e=G[v][i];
                if(d[e.to]>d[v]+e.cost){
                    d[e.to]=d[v]+e.cost;
                    que.push(l_l(d[e.to],e.to));
                }
            }
        }
    }
}

int main(){fastio
    ll n,m;cin>>n>>m;
    ll a[m],b[m];
    rep(i,0,m-1){
        cin>>a[i]>>b[i];
        edge e;
        e.to=b[i];e.cost=1;
        G[a[i]].pb(e);
        e.to=a[i];e.cost=1;
        G[b[i]].pb(e);
    }
    ll k;cin>>k;
    ll c[k];rep(i,0,k-1)cin>>c[i];
    ll l[k][k]; //c[i]からc[j]への最短距離
    rep(i,0,k-1){
        dijkstra(c[i]);
        rep(j,0,k-1){
            l[i][j] = d[c[j]];
        }
    }
    /*
    rep(i,0,k-1){
        rep(j,0,k-1){
            cout<<l[i][j]<<' ';
        }
        cout<<endl;
    }
    */
    ll L=(1<<k);
    ll dp[L][k];rep(i,0,L-1)rep(j,0,k-1)dp[i][j]=inf;
    rep(i,0,k-1){
        dp[(1<<i)][i]=0;
    }
    rep(i,0,L-1){
        rep(j,0,k-1){
            if(!((i>>j)&1)){
                continue;
            }
            ll M=i-(1<<j);
            rep(ii,0,k-1){
                if((M>>ii)&1){
                    dp[i][j] = min(dp[i][j],dp[M][ii]+l[ii][j]);
                }
            }
        }
    }
    ll ans=inf;
    rep(i,0,k-1){
        ans=min(ans,dp[L-1][i]);
    }
    if(ans>=inf){
        cout<<-1<<endl;
    }else{
        cout<<ans+1<<endl;
    }
    
    return 0;
    
}






/*************************************************************************
  > File Name: solve.cpp
  > Author: liupo
  > Mail: lanzongwei@gmail.com
  > Created Time: 2021-02-28 21:37:24
 ************************************************************************/

#define GOODOJ
#define SYNC 0

#ifdef GOODOJ
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <chrono>
#include <random>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#else
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <limits>
#include <cassert>
#include <sstream>
#include <iterator>
#include <functional>
#endif
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define rap(i,x) for(auto& i : (x))
#define seg(t) (t).begin(), (t).end()
#define ep emplace_back
#define mkp make_pair
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second
#define lowbit(x) ((-(x))&(x))
#define RE register
#define getchar() getchar_unlocked()
#ifdef DEBUG
void err(istream_iterator<string>){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ';
	err(++it, args...);
}
#define debug(args...) {string _s=#args;replace(seg(_s),',',' ');\
	cerr<<"DEBUG:";istringstream it(_s);\
	err(istream_iterator<string>(it), args);cerr<<endl;}
#else
#define debug(...)
#endif

template<typename T> inline bool cmax(T& a,const T& b) {return a<b?a=b,1:0;}
template<typename T> inline bool cmin(T& a,const T& b) {return a>b?a=b,1:0;}

#ifdef GOODOJ
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef __gnu_pbds::priority_queue<int> pq;
#endif
typedef std::string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pa;

const double P = acos(-1.0), eps = 1e-9;
struct point { db x ,y;};
inline int sign(db a) {return a < -eps ? -1 : a > eps;}
#define dot(p1,p2,p3) ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))

constexpr int Ma = 1e6, inf = 0x3f3f3f3f, mod = 1e9 + 7;

int who[200];

void solve() {
	str s[3]; rep (i, 3) cin >> s[i];
	set<int> cnt;
	rep (i, 3) rap (j, s[i]) cnt.emplace(j);
	if (cnt.size() > 10) {
		cout << "UNSOLVABLE" << endl;
		return ;
	}
	vector<int> id(10);
	iota(seg(id), 0);
	int ct = 0;
	rap (i, cnt) who[i] = ct++;
	do {
		bool show = true;
		rep (i, 3)
			if (id[who[s[i][0]]] == 0) {
				show = false;
				break;
			}
		if (not show) continue;
		ll num[3] = {0, 0, 0};
		rep (i, 3) {
			rap (j, s[i]) num[i] *= 10, num[i] += id[who[j]];
		}
		if (num[0] + num[1] == num[2]) {
			cout << num[0] << endl << num[1] << endl << num[2] << endl;
			return ;
		}
	} while (next_permutation(seg(id)));
	cout << "UNSOLVABLE" << endl;
}

signed main() {
#if SYNC==0
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	int T = 1;
	while (T--) solve();

	return 0;
}