# include <bits/stdc++.h>
# define int long long
# define wheneveright signed main
using namespace std;

const int maxn = 100005;
const int maxe = 400005;

struct reader {
	template <typename Type>
	reader & operator >> (Type & ret) {
		int f = 1; ret = 0; char ch = getchar ();
		for (;!isdigit (ch); ch = getchar ()) if (ch == '-') f = -f;
		for (; isdigit (ch); ch = getchar ()) ret = ret * 10 + ch - '0';
		ret *= f; return * this;
	}
} fin;

int n, m, k;
int t[maxn];
int x, y;

int dis[2][maxn];
struct WER {
	int pos, dis;
	bool operator < (WER p) const {
		return dis > p.dis;
	}
} now;
priority_queue < WER > que;

bool vis[2][maxn], isp[maxn];
int res[maxn];

queue < int > q;

struct Graph {
	int lnk[maxn], nxt[maxe], son[maxe], tot;
	void add_e (int x, int y) {
		nxt[++tot] = lnk[x]; lnk[x] = tot; son[tot] = y;
		nxt[++tot] = lnk[y]; lnk[y] = tot; son[tot] = x;
		return ;
	}
	void Dijkstra (int s, int p) {
		while (!que.empty ()) que.pop ();
		memset (dis[p], 127, sizeof dis[p]);
		que.push ((WER) { s, dis[p][s] = t[s] });
		while (!que.empty ()) {
			now = que.top (); que.pop ();
			if (now.dis != dis[p][now.pos]) continue ;
			for (int j = lnk[now.pos]; j; j = nxt[j])
				if (dis[p][son[j]] > now.dis + t[son[j]])
					que.push ((WER) { son[j], dis[p][son[j]] = now.dis + t[son[j]] });
		}
		return ;
	}
	void solve () {
		bool p = (k > m);
		for (int j = lnk[1]; j; j = nxt[j]) vis[0][son[j]] = 1;
		for (int i = 1; i <= n; i++)
			for (int j = lnk[i]; j; j = nxt[j])
				if (son[j] == n) vis[1][i] = 1;
		if (vis[1][1] || vis[0][n]) {
			if (p) res[1] = res[n] = 1, k -= 2;
			else   res[1] = res[n] = 2, m -= 2;
			for (int i = 2; i < n; i++)
				if (vis[0][i] && vis[1][i]) {
					if (p) res[i] = 1, k--;
					else   res[i] = 2, m--;
				}
		}
		if (k < 0 || m < 0) return puts ("impossible"), void ();
		while (!q.empty ()) q.pop ();
		q.push (1);
		while (!q.empty () && k > 0) {
			int now = q.front (); q.pop ();
			if (!res[now]) res[now] = 1, k--;
			for (int j = lnk[now]; j; j = nxt[j])
				if (!isp[son[j]]) {
					isp[son[j]] = true;
					q.push (son[j]);
				}
		}
		for (int i = 1; i <= n; i++)
			if (!res[i]) {
				if (k > 0) res[i] = 1, k--;
				else res[i] = 2;
			}
		for (int i = 1; i <= n; i++)
			putchar ("UP"[res[i] - 1]);
		return ;
	}
} A, B;

int Dis;

wheneveright () {
	fin >> n >> m >> k;
	for (int i = 1; i <= n; i++) fin >> t[i];
	while (m--) fin >> x >> y, A.add_e (x, y);
	A.Dijkstra (1, 0); A.Dijkstra (n, 1);
	Dis = dis[0][n]; m = n - k;
	if (Dis == dis[0][0]) {
		while (k--) putchar ('U');
		while (m--) putchar ('P');
		return 0;
	}
	for (int i = 1; i <= n; i++)
		for (int j = A.lnk[i]; j; j = A.nxt[j])
			if (dis[0][i] + dis[1][A.son[j]] == Dis)
				B.add_e (i, A.son[j]);
	B.solve ();
	return 0;
}