#include<bits/stdc++.h>
using namespace std;
const int Max_N=1e5,Max_M=2e5,Inf=(1e9)+1;
int n,m,K,Num,lin[Max_N+5],t[Max_N+5],dis[Max_N+5],Dis[Max_N+5],vis[Max_N+5],In[Max_N+5];
char ans[Max_N+5];
priority_queue< pair<int,int> > Q;
queue<int> q;
vector<int> a[Max_N+5];
struct Edge{
	int Id,Next;
} e[Max_M*2+5];
struct EDGE{
	int u,v;
} E[Max_M+5];
void Insert(int x,int y){
	e[++Num].Next=lin[x]; lin[x]=Num; e[Num].Id=y;
}
int main(){
	scanf("%d%d%d",&n,&m,&K);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&E[i].u,&E[i].v);
		Insert(E[i].u,E[i].v); 
		Insert(E[i].v,E[i].u);
	}
	for(int i=1;i<=n;i++) dis[i]=Inf;
	dis[1]=t[1]; Q.push(make_pair(-dis[1],1));
	for(;Q.size();){
		int x=Q.top().second; Q.pop();
		if(vis[x]) continue; vis[x]=1;
		for(int i=lin[x];i;i=e[i].Next)
		 if(dis[x]+t[e[i].Id]<dis[e[i].Id]){
		 	dis[e[i].Id]=dis[x]+t[e[i].Id];
		 	Q.push(make_pair(-dis[e[i].Id],e[i].Id));
		 }
	}
	if(dis[n]==2){
		if(K>=2){
			putchar('N'); K-=2;
			for(int i=2;i<n;i++)
			 if(K) putchar('N'),--K;
			 else putchar('S');
			putchar('N'); puts("");
		} else if(n-K>=2){
			putchar('S');
			for(int i=2;i<=n;i++)
			 if(K) putchar('N'),--K;
			 else putchar('S');
			puts("");
		} else {
			puts("impossible");
			return 0;
		}
	}
	for(int i=1;i<=n;i++) Dis[i]=Inf,vis[i]=0;
	Dis[n]=t[n]; Q.push(make_pair(-Dis[n],n));
	for(;Q.size();){
		int x=Q.top().second; Q.pop();
		if(vis[x]) continue; vis[x]=1;
		for(int i=lin[x];i;i=e[i].Next)
		 if(Dis[x]+t[e[i].Id]<Dis[e[i].Id]){
		 	Dis[e[i].Id]=Dis[x]+t[e[i].Id];
		 	Q.push(make_pair(-Dis[e[i].Id],e[i].Id));
		 }
	}
	for(int i=1;i<=m;i++){
		if(dis[E[i].u]+Dis[E[i].v]==dis[n])
		 a[E[i].u].push_back(E[i].v),++In[E[i].v];
		if(dis[E[i].v]+Dis[E[i].u]==dis[n])
		 a[E[i].v].push_back(E[i].u),++In[E[i].u];
	}
	q.push(1);
	for(int i=1;i<=n;i++) vis[i]=0;
	for(;q.size();){
		int x=q.front(); q.pop(); vis[x]=1;
		if(K) ans[x]='N',--K;
		else ans[x]='S';
		for(int i=0;i<a[x].size();i++){
			--In[a[x][i]];
			if(In[a[x][i]]==0) q.push(a[x][i]);
		}
	}
	for(int i=1;i<=n;i++)
	 if(!vis[i]){
	 	if(K) ans[i]='N',--K;
	 	else ans[i]='S';
	 }
	for(int i=1;i<=n;i++) printf("%c",ans[i]);
	puts("");
	return 0;
} 

answer.code:1:9: fatal error: bits/stdc++.h: No such file or directory
 #include<bits/stdc++.h>
         ^~~~~~~~~~~~~~~
compilation terminated.