#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
const int MAXN=1e5+10,INF=0x3f3f3f3f;
int n,m,qn,C[MAXN]; bool bleaf[MAXN];
mt19937 rng;
struct _T{
    vector<int> G[MAXN]; set<pair<int,int>> Gs[MAXN];
    int dfn[MAXN],fa[MAXN],dfnc,siz[MAXN],dfns[MAXN],val1[MAXN];
    struct FhqTreap{
        struct{ int fa,ls,rs,sz,pri,mn,val,tag; } T[MAXN];
        void pushup(int u){
            T[u].sz=T[T[u].ls].sz+T[T[u].rs].sz;
            T[u].mn=min({T[T[u].ls].mn+T[T[u].ls].tag,T[T[u].rs].mn+T[T[u].rs].tag,T[u].val});
        }
        void pushdown(int u){
            if(T[u].ls) T[T[u].ls].tag+=T[u].tag;
            if(T[u].rs) T[T[u].rs].tag+=T[u].tag;
            T[u].tag=0;
        }
        int pos(int u){
            int c=1+T[T[u].ls].sz;
            for(int lst=u,u=T[u].fa; u; lst=u,u=T[u].fa){
                if(lst==T[u].rs) c+=1+T[T[u].ls].sz;
            }
            return c;
        }
        pair<int,int> split(int u,int c){
            if(!u) return {0,0};
            assert(0<=c&&c<=T[u].sz);
            if(!c) return {0,u};
            if(c==T[u].sz) return {u,0};
            pushdown(u);
            T[u].fa=0;
            if(c<=T[T[u].ls].sz){
                auto [v1,v2]=split(T[u].ls,c);
                T[u].ls=v2,T[v2].fa=u,pushup(u);
                return {v1,u};
            }else{
                c-=T[T[u].ls].sz+1;
                auto [v1,v2]=split(T[u].rs,c);
                T[u].rs=v1,T[v1].fa=u,pushup(u);
                return {u,v2};
            }
        }
        int merge(int u,int v){
            if(!u||!v) return u|v;
            if(T[u].pri<T[v].pri){
                pushdown(u);
                int w=merge(T[u].rs,v);
                T[u].rs=w,T[w].fa=u;
                pushup(u);
                return u;
            }else{
                pushdown(v);
                int w=merge(u,T[v].ls);
                T[v].ls=w,T[w].fa=u;
                pushup(v);
                return v;
            }
        }
        int build(int fa,int l,int r){
            if(l>r) return 0;
            int mid=(l+r)/2,u=dfns[mid];
            T[u]={fa,build(u,l,mid-1),build(u,mid+1,r),1,int(rng()),0,val1[u],0};
            pushup(u);
        }
        void add(int p,int len,int x){
            if(len==1){
                int u=p;
                T[u].tag+=x;
                if(T[u].ls) T[T[u].ls].tag-=x;
                if(T[u].rs) T[T[u].rs].tag-=x;
                while(u) pushup(u),u=T[u].fa;
            }
            int i=pos(p);
            int u,v,w;
            tie(u,v)=split(rt,i-1);
            tie(v,w)=split(v,len);
            T[v].tag+=x;
            rt=merge(merge(u,v),w);
        }
    } T;
    void dfs(int u,int fa_){
        dfn[u]=++dfnc,fa[u]=fa_,dfns[dfnc]=u;
        if(fa_) val1[u]=val1[fa_]+(C[u]!=C[fa_]);
        sort(G[u].begin(),G[u].end(),[](auto v1,auto v2){ return C[v1]<C[v2]; });
        for(int v:G[u]){
            if(v==fa_) continue;
            Gs[u].push_back({col[v],v});
            dfs(v,u);
            siz[u]+=siz[v];
        }
    }
    void init(){
        T.T[0].mn=INF;
        dfs(1,0);
        T.rt=T.build(0,1,n);
    }
    void upd(int u,int c){
        auto do_[u](int op){
            if(fa[u]){
                T.add(u,siz[u],(col[u]==col[fa[u]]+1)*op);
                T.add(u,1,-op);
            }
        };
    }
} T1,T2;
vector<int> G[MAXN]; pii E[MAXN];
bool vis[MAXN],instk[MAXN],done;
int fa[MAXN];
void dfs(int u,int fa_){
    if(done) return;
    fa[u]=fa_,vis[u]=1,instk[u]=1;
    for(int v:G[u]){
        if(v==fa_) continue;
        if(vis[v]){
            for(int w:G[v]){
                if(w!=u&&w!=fa[v]&&instk[w]){
                    RNG(i,1,m){
                        auto [p,q]=E[i];
                        if(!(p==min(u,v)&&q==max(u,v))) T1.G[p].push_back(q),T1.G[q].push_back(p);
                    }
                    RNG(i,1,m){
                        auto [p,q]=E[i];
                        if(!(p==min(v,w)&&q==max(v,w))) T2.G[p].push_back(q),T2.G[q].push_back(p);
                    }
                    done=1;
                    return;
                }
            }
            assert(0);
        }
        if(done) return;
    }
    instk[u]=0;
}
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
#endif
    { int _; cin>>n>>m>>qn>>_; }
    RNG(u,1,n) cin>>C[u];
    RNG(i,1,m,u,v) cin>>u>>v,G[u].push_back(v),G[v].push_back(u),E[i]={min(u,v),max(u,v)};
    RNG(u,1,n) bleaf[u]=(G[u].size()==1)
    if(m==n-1){
        copy_n(G+1,n,T1.G+1);
        T1.init();
    }else{
        dfs(1,0); assert(done);
        T1.init(),T2.init();
    }
}