// D - RGB Coloring 2
// sample code
// reference: https://atcoder.jp/contests/abc199/submissions/22053625
#include <bits/stdc++.h>
using namespace std;
#define vec vector
using vi = vec<int>;
using ll = int64_t;
#define rep(i,e) for(int i=0;i<(e);++i)

vec<vi> G;
vi IX; //彩色順を記録。違う連結成分なら同じ index もある

ll dfs(int now, vi&v){
	ll res = 0;
	for(int to:G[now]) if(v[to] == v[now]) return res; // 隣接色かぶり
	res = 1;
	for(int to:G[now]){ // 隣接点
		if(IX[to] == -1) IX[to] = IX[now] + 1; // 未訪問->彩色順を採番
		if(IX[to] != IX[now] + 1) continue; // 彩色順どおりでない->訪問済み
		ll tmp = 0;
		rep(i, 2){
			v[to] = (v[now] + i+1) % 3; // 隣接点を彩色
			tmp += dfs(to, v); // 隣接点へ
		}
		v[to] = -1; // 無色に戻す
		res *= tmp;
		if (tmp == 0) break;
		// tmp == 0 の時、早期に return してるので
		// IX が振り切れていない事に注意
	}
 	return res;
}

int main(){
	int n, m; cin>>n>> m;
	G.resize(n);
	rep(i, m){
		int a, b; cin>>a>>b; --a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	IX.resize(n, -1);
	vi v(20, -1); // 彩色された点
	ll ans = 1;
	rep(i, n){
		if(IX[i] != -1) continue; // 採番済み->訪問済み
		IX[i] = v[i] = 0; // 開始点の訪問済み＆彩色
		ans *= dfs(i, v) * 3;
	}
	cout<< ans <<endl;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    ll N, L;
    cin >> N >> L;
    vector<ll> A(N+3), B(N+2);
    for (ll i = 0; i < N; i++) {
        cin >> A[i+1];
    }
    for (ll i = 0; i < N; i++) {
        cin >> B[i+1];
    }
    A[0] = 0; A[N+1] = L+1; A[N+2] = L+3; B[N+1] = L+3;

    vector<ll> J(N+2);
    ll tmpj = 0;
    for (int i = 1; i <= N; i++) {
        while(tmpj <= N+1){
            if(B[i] == A[tmpj] - (tmpj - i)){
                J[i] = tmpj;
                break;
            }
            tmpj++;
        }
    }
    if(tmpj == N+2){
        printf("%d\n", -1);
        return 0;
    }
    J[N+1] = N+3;

    ll ans = 0;
    J[0] = -1;
    for (ll i = 1; i <= N; i++) {
        if(J[i] == J[i-1]) continue;
        ll mi, ma; mi = min(i, J[i]); ma = max(i, J[i]);
        ll tmpi = i;
        while(J[tmpi] == J[i]){
            mi = min(mi, tmpi);
            ma = max(ma, tmpi);
            tmpi++;
        }
        ans += ma - mi;
        // printf("%lld %lld %lld\n", J[i], mi, ma);
        ll tmp = 0;
        tmpi = J[i] - 1;
        while(tmpi >= mi && A[tmpi] + 1 == A[tmpi+1]){
            tmp++;
            tmpi--;
        }
        tmpi = J[i] + 1;
        while(tmpi <= ma && A[tmpi-1] + 1 == A[tmpi]){
            tmp++;
            tmpi++;
        }
        // for (int j = mi; j < ma+1; j++) {
        //     if(j == J[i]) continue;
        //     if(A[j] == B[j]){
        //         tmp++;
        //     }
        // }
        ans -= tmp;
    }

    // for (int i = 1; i <= N; i++) {
    //     printf("%lld\n", J[i]);
    // }
    printf("%lld\n", ans);


    


}