#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0, length = n; i < length; i++)
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ep emplace
#define epb emplace_back
#define scll static_cast<long long> 
#define sz(x) static_cast<int>((x).size())
#define pfll(x) printf("%lld\n", x)
#define ci(x) cin >> x
#define ci2(x, y) cin >> x >> y
#define ci3(x, y, z) cin >> x >> y >> z
#define ci4(w, x, y, z) cin >> w >> x >> y >> z
#define co(x) cout << x << endl
#define co2(x, y) cout << x << " " << y << endl
#define co3(x, y, z) cout << x << " " << y << " " << z << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> PQ;
typedef priority_queue<int, vector<int>, greater<int>> PQG;
typedef priority_queue<P> PQP;
typedef priority_queue<P, vector<P>, greater<P>> PQPG;

const int MAX_N = 2e5, MOD = 1e9 + 7, INF = 1e9;
char c[20];
int n, m;
ll cnt[20];
bool jdg[20];
vector<char> to[20];
vector<vector<char>> v;

void dfs1(char x) {
    if (jdg[x]) return;
    jdg[x] = true;
    v.back().epb(x);
    for (auto &i: to[x]) dfs1(i);
    return;
}

void dfs2(char x, char y) {
    if (c[v[x][y]] >= 0) return;
    rep(i, 3) {
        bool con = false;
        for (auto &j: to[v[x][y]]) {
            if (i == c[j]) {
                con = true;
                break;
            }
        }
        if (con) continue;
        c[v[x][y]] = i;
        if (y + 1 < v[x].size()) dfs2(x, y + 1);
        else cnt[x]++;
    }
    c[v[x][y]] = -1;
    return;
}

int main() {
    ci2(n, m);
    rep(i, m) {
        int a, b;
        ci2(a, b);
        to[a - 1].epb(b - 1);
        to[b - 1].epb(a - 1);
    }
    rep(i, n) {
        if (jdg[i]) continue;
        v.epb(vector<char>(0));
        dfs1(i);
    }
    fill(c, c + n, -1);
    rep(i, v.size()) dfs2(i, 0);
    ll ans = 1;
    rep(i, v.size()) ans *= cnt[i];
    co(ans);
    return 0;
}

//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++){for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << p.first << " " << p.second;}
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){for(auto &z:v)os << z << " ";cout<<"|"; return os;}
template<typename T>void rearrange(vector<ll>&ord, vector<T>&v){
  auto tmp = v;
  for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
}
template<typename Head, typename... Tail>void rearrange(vector<ll>&ord,Head&& head, Tail&&... tail){
  rearrange(ord, head);
  rearrange(ord, tail...);
}
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int popcount(ll x){return __builtin_popcountll(x);};
int poplow(ll x){return __builtin_ctzll(x);};
int pophigh(ll x){return 63 - __builtin_clzll(x);};

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n,m;cin>>n>>m;
  struct edge{
    ll to,id,rev;
  };
  vector<vector<edge>>g(n);
  rep(i,0,m){
    ll u,v;cin>>u>>v;u--;v--;
    g[u].PB({v,i,0});
    g[v].PB({u,i,1});
  }
  vector<ll>c(n);
  rep(i,0,n)cin>>c[i];
  vector<ll>ord(n);
  iota(ALL(ord),0);
  sort(ALL(ord),[&](ll i,ll j)
    {
      return c[i]<c[j];
    }
  );
  vector<bool>used(n);
  vector<ll>ed(m,-1);
  for(auto i:ord){
    if(used[i])continue;
    auto dfs=[&](auto &&f,ll k)->void{
      used[k]=true;
      for(auto e:g[k]){
        if(ed[e.id]!=-1)continue;
        if(c[e.to]>c[i])continue;
        ed[e.id]=e.rev;
        if(used[e.to])continue;
        f(f,e.to);
      }
    };
    dfs(dfs,i);
  }
  //debug(ed,m);
  rep(i,0,m){
    ans(!ed[i],"->","<-");
  }
  return 0;
}