#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5, INF=2e9;
int n, m;
int a[MAXN];
vector<int> adj[MAXN];
int link[MAXN], csize[MAXN], cindex[MAXN];
long long sum[MAXN];
set<pair<int, int> > neighbours[MAXN];
bool compare(int x, int y)
{
return a[x]<a[y];
}
int find(int x)
{
if (x==link[x])
return x;
return link[x]=find(link[x]);
}
void unite(int x, int y, int maxvalue)
{
x=find(x);
y=find(y);
if (neighbours[cindex[x]].size()<neighbours[cindex[y]].size())
swap(x, y);
for (auto t : neighbours[cindex[y]])
if (t.first>maxvalue)
neighbours[cindex[x]].insert(t);
neighbours[cindex[y]].clear();
cindex[y]=cindex[x];
if (csize[x]<csize[y])
swap(x, y);
csize[x]=csize[x]+csize[y];
sum[x]=sum[x]+sum[y];
link[y]=x;
return;
}
vector<bool> brute()
{
vector<bool> possible(n, 0);
for (int i=0; i<n; i++)
{
priority_queue<pair<int, int> > pq;
pq.push({-a[i], i});
long long sum=0;
bool visited[n]={false};
while (!pq.empty())
{
int x=pq.top().second;
pq.pop();
if (x!=i && sum<a[x])
continue;
if (visited[x])
continue;
visited[x]=true;
sum=sum+a[x];
for (auto y : adj[x])
if (!visited[y])
pq.push({-a[y], y});
}
if (*min_element(visited, visited+n)==1)
possible[i]=true;
}
return possible;
}
int main()
{
//ios_base::sync_with_stdio(0);
//cin.tie(0);
srand(time(0));
int tc=0;
//cin >> tc;
//while (true)
{
/*n=rand()%5+1;
m=n-1+rand()%5;
if (m>n*(n-1)/2)
continue;
tc=tc+1;
cout << "tc " << tc << '\n';
for (int i=0; i<n; i++)
{
adj[i].clear();
neighbours[i].clear();
}
for (int i=0; i<n; i++)
a[i]=rand()%5+1;
set<pair<int, int> > used;
for (int x=1; x<n; x++)
{
int y=rand()%x;
adj[x].push_back(y);
adj[y].push_back(x);
used.insert({x, y});
}
while (used.size()<m)
{
int x=rand()%n;
int y=rand()%n;
if (x==y)
continue;
if (used.count({x, y}) || used.count({y, x}))
continue;
adj[x].push_back(y);
adj[y].push_back(x);
used.insert({x, y});
}*/
cin >> n >> m;
for (int i=0; i<n; i++)
cin >> a[i];
for (int i=0; i<m; i++)
{
int x, y;
cin >> x >> y;
adj[x-1].push_back(y-1);
adj[y-1].push_back(x-1);
}
/*cin >> n >> m;
for (int i=0; i<n; i++)
cin >> a[i];
for (int i=0; i<m; i++)
{
int x, y;
cin >> x >> y;
adj[x-1].push_back(y-1);
adj[y-1].push_back(x-1);
}*/
int sorted[n];
for (int i=0; i<n; i++)
sorted[i]=i;
sort(sorted, sorted+n, compare);
for (int i=0; i<n; i++)
{
link[i]=i;
csize[i]=1;
sum[i]=a[i];
cindex[i]=i;
for (auto x : adj[i])
neighbours[i].insert({a[x], x});
}
map<int, vector<int> > byvalue;
for (int i=0; i<n; i++)
byvalue[a[i]].push_back(i);
bool possible[n];
for (int i=0; i<n; i++)
possible[i]=true;
queue<int> q;
for (auto k : byvalue)
{
for (auto x : k.second)
{
for (auto y : adj[x])
if (a[y]<=a[x] && find(x)!=find(y))
unite(x, y, a[x]);
}
for (auto x : k.second)
{
int leader=find(x);
while (!neighbours[cindex[leader]].empty() && (*neighbours[cindex[leader]].begin()).first<=a[x])
neighbours[cindex[leader]].erase(neighbours[cindex[leader]].begin());
if (neighbours[cindex[leader]].empty())
continue;
auto it=neighbours[cindex[leader]].begin();
//cout << "x sum min " << x << ' ' << sum[leader] << ' ' << (*it).first << '\n';
if (sum[leader]>=(*it).first)
continue;
possible[x]=false;
q.push(x);
while (!q.empty())
{
int y=q.front();
q.pop();
for (auto t : adj[y])
if (a[t]<=a[x] && possible[t])
{
possible[t]=false;
q.push(t);
}
}
}
}
for (int i=0; i<n; i++)
cout << possible[i];
/*auto br=brute();
bool flop=false;
for (int i=0; i<n; i++)
if (possible[i]!=br[i])
flop=true;
if (flop)
{
cout << "FLOP\n";
cout << n << ' ' << m << '\n';
for (int i=0; i<n; i++)
cout << a[i] << ' ';
cout << '\n';
for (auto edge : used)
cout << edge.first << ' ' << edge.second << '\n';
for (int i=0; i<n; i++)
cout << possible[i];
cout << '\n';
for (int i=0; i<n; i++)
cout << br[i];
cout << '\n';
break;
}*/
}
return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5, INF=2e9;
int n, m;
int a[MAXN];
vector<int> adj[MAXN];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i=0; i<n; i++)
cin >> a[i];
for (int i=0; i<m; i++)
{
int x, y;
cin >> x >> y;
adj[x-1].push_back(y-1);
adj[y-1].push_back(x-1);
}
set<int> values;
for (int i=0; i<n; i++)
values.insert(-a[i]);
bool possible[n]={false};
queue<int> q;
for (auto kt : values)
{
int k=-kt;
bool visited[n]={false};
for (int i=0; i<n; i++)
{
if (a[i]!=k || visited[i])
continue;
visited[i]=true;
long long sum=a[i];
q.push(i);
vector<int> nodes;
nodes.push_back(i);
int minsum=INF;
while (!q.empty())
{
int x=q.front();
q.pop();
for (auto y : adj[x])
{
if (a[y]<=k && !visited[y])
{
visited[y]=true;
sum=sum+a[y];
q.push(y);
if (a[y]==k)
nodes.push_back(y);
}
if (a[y]>k && possible[y])
minsum=min(minsum, a[y]);
}
}
if (minsum>sum && k!=-(*values.begin()))
continue;
for (auto x : nodes)
possible[x]=true;
}
}
for (int i=0; i<n; i++)
cout << possible[i];
return 0;
}*/
/*#include <bits/stdc++.h>
using namespace std;
const int MAXN=300000;
int n, m;
int a[MAXN];
vector<int> adj[MAXN];
long long prefix[MAXN];
bool compare(int x, int y)
{
return a[x]>a[y];
}
long long sum(int l, int r)
{
if (l==0)
return prefix[r];
return prefix[r]-prefix[l-1];
}
vector<bool> brute()
{
vector<bool> possible(n, 0);
for (int i=0; i<n; i++)
{
priority_queue<pair<int, int> > pq;
pq.push({-a[i], i});
long long sum=0;
bool visited[n]={false};
while (!pq.empty())
{
int x=pq.top().second;
pq.pop();
if (x!=i && sum<a[x])
continue;
if (visited[x])
continue;
visited[x]=true;
sum=sum+a[x];
for (auto y : adj[x])
if (!visited[y])
pq.push({-a[y], y});
}
if (*min_element(visited, visited+n)==1)
possible[i]=true;
}
return possible;
}
int main()
{
//ios_base::sync_with_stdio(0);
//cin.tie(0);
srand(time(0));
int tc=0;
//cin >> tc;
//while (true)
{
tc=tc+1;
cout << "tc " << tc << '\n';
n=rand()%100+1, m=0;
for (int i=0; i<n; i++)
a[i]=rand()%100000+1;
//for (int i=0; i<n; i++)
// cout << a[i] << ' ';
//cout << '\n';
cin >> n >> m;
for (int i=0; i<n; i++)
cin >> a[i];
for (int i=0; i<n; i++)
adj[i].clear();
for (int i=0; i<m; i++)
{
int x, y;
cin >> x >> y;
adj[x-1].push_back(y-1);
adj[y-1].push_back(x-1);
}
int sorted[n];
for (int i=0; i<n; i++)
sorted[i]=i;
sort(sorted, sorted+n, compare);
int possible[n]={false};
possible[sorted[0]]=true;
set<int> larger;
larger.insert(sorted[0]);
prefix[0]=a[0];
for (int i=1; i<=n; i++)
prefix[i]=prefix[i-1]+a[i];
for (int i=1; i<n; i++)
{
int x=sorted[i];
int l=-1, r=n;
auto it=larger.lower_bound(x);
if (it!=larger.end())
r=*it;
if (it!=larger.begin())
{
it--;
l=*it;
}
if (l!=-1 && possible[l] && sum(l+1, r-1)>=a[l])
possible[x]=true;
if (r!=n && possible[r] && sum(l+1, r-1)>=a[r])
possible[x]=true;
larger.insert(x);
}
for (int i=0; i<n; i++)
cout << possible[i];
auto br=brute();
bool flop=false;
for (int i=0; i<n; i++)
if (possible[i]!=br[i])
flop=true;
if (flop)
{
cout << "FLOP\n";
cout << n << '\n';
for (int i=0; i<n; i++)
cout << a[i] << ' ';
cout << '\n';
for (int i=0; i<n; i++)
cout << possible[i];
cout << '\n';
for (int i=0; i<n; i++)
cout << br[i];
cout << '\n';
break;
}
}
return 0;
}*/
