#include #include #include #include namespace atcoder { // Implement (union by size) + (path compression) // Reference: // Zvi Galil and Giuseppe F. Italiano, // Data structures and algorithms for disjoint set union problems struct dsu { public: dsu() : _n(0) {} dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector parent_or_size; }; } // namespace atcoder using namespace std; using namespace atcoder; using ll=long long; #define rng(i,l,r) for(int i=int(l);i=int(l);i--) #define rrep(i,r) rrng(i,0,r) #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define F first #define S second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #define inf INT_MAX/2-100 #define infl LLONG_MAX/3 #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<' '<<#x<<' '<bool chmax(t&a,u b){if(abool chmin(t&a,u b){if(busing vc=vector; templateusing vvc=vector>; using pi=pair; using pl=pair; using vi=vc; using vl=vc; ll readl(void){ ll x; cin>>x; return x; } int readi(void){ int x; cin>>x; return x; } string readstr(){ string s; cin>>s; return s; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=readi(),v[i]+=off; return v; } vl readvl(int n,int off=0){ vl v(n); rep(i,n)v[i]=readl(),v[i]+=off; return v; } template void print(t x,int suc=1){ cout< void print(const vc&v,int suc=1){ rep(i,si(v))print(v[i],i==int(si(v))-1?1:suc); } template bool inc(t a,t b,t c){ return !(c void compress(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } template struct Compress{ vcv; Compress()=default; Compress(const vc&x){ add(x); } Compress(const initializer_list >&x){ for(auto &p:x)add(p); } void add(const t&x){ v.eb(x); } void add(const vc&x){ copy(all(x),back_inserter(v)); } void build(){ compress(v); } int get(const t&x)const{ return lwb(v,x); } vcget(const vc&x)const{ vcres(x); for(auto &p:res)p=get(p); return res; } const t &operator[](int x)const{ return v[x]; } int size(){ return v.size(); } }; void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); } void orYes(bool x,bool ex=true){ if(x)Yes(ex); else No(ex); } void orYES(bool x,bool ex=true){ if(x)YES(ex); else NO(ex); } void Possible(bool ex=true){ cout<<"Possible\n"; if(ex)exit(0); } void POSSIBLE(bool ex=true){ cout<<"POSSIBLE\n"; if(ex)exit(0); } void Impossible(bool ex=true){ cout<<"Impossible\n"; if(ex)exit(0); } void IMPOSSIBLE(bool ex=true){ cout<<"IMPOSSIBLE\n"; if(ex)exit(0); } void orPossible(bool x,bool ex=true){ if(x)Possible(ex); else Impossible(ex); } void orPOSSIBLE(bool x,bool ex=true){ if(x)POSSIBLE(ex); else IMPOSSIBLE(ex); } using uint=unsigned; using ull=unsigned long long; template struct Modular{ static constexpr uint const &mod=MOD; uint v; Modular(long long x=0){c(x%mod+mod);} Modular& c(uint x){ v=x>=1; } return res; } Modular inv()const{return pow(mod-2);} Modular operator-()const{return Modular(mod-v);} Modular& operator+=(const Modular &x){return c(v+x.v);} Modular& operator-=(const Modular &x){return c(v+mod-x.v);} Modular& operator*=(const Modular &x){v=ull(v)*x.v%mod;return *this;} Modular& operator/=(const Modular &x){return *this*=x.inv();} Modular operator+(const Modular &x)const{return Modular(*this)+=x;} Modular operator-(const Modular &x)const{return Modular(*this)-=x;} Modular operator*(const Modular &x)const{return Modular(*this)*=x;} Modular operator/(const Modular &x)const{return Modular(*this)/=x;} friend Modular operator+(long long x,const Modular &y){return Modular(x)+y;} friend Modular operator-(long long x,const Modular &y){return Modular(x)-y;} friend Modular operator*(long long x,const Modular &y){return Modular(x)*y;} friend Modular operator/(long long x,const Modular &y){return Modular(x)/y;} friend ostream& operator<<(ostream&os,const Modular&x){ return os<>(istream&is,Modular&x){ long long p; is>>p; x=Modular(p); return is; } bool operator==(const Modular &x)const{return v==x.v;} bool operator!=(const Modular &x)const{return v!=x.v;} bool operator<(const Modular &x)const{return v; vectorfact,finv,invs; void Initfact(int n=(1<<21)+10){ fact.resize(n+1),finv.resize(n+1),invs.resize(n+1); fact[0]=1; for(int i=1;i<=n;i++){ fact[i]=fact[i-1]*i; } finv[n]=fact[n].inv(); for(int i=n-1;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } invs[0]=1; for(int i=0;i<=n;i++){ invs[i]=finv[i]*fact[i-1]; } } Mint comb(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } ll gcd(ll a,ll b){ if(a>n>>m>>s>>t; s--,t--; vi cm; rep(i,n){ cin>>p[i]; cm.pb(p[i]); } sort(all(cm)); cm.erase(unique(all(cm)),cm.end()); rep(i,n){ p[i]=lwb(cm,p[i]); q[p[i]].pb(i); } rep(i,m){ int a,b; cin>>a>>b; g[--a].pb(--b); g[b].pb(a); } dsu uf(n); for(int i=si(cm)-1;i>=0;i--){ for(auto v:q[i]){ for(auto u:g[v]){ if(p[u]>=i)uf.merge(v,u); } } if(i>=p[s])continue; bool ok=false; for(auto v:q[i]){ if(uf.same(s,v))ok=true; } if(ok)ans++; } print(ans); }