题目描述
UR#24 的题面被内鬼偷走了！
为了找回丢失的题面，uoj 管理员决定和 pjudge 管理员合作，让内鬼无路可逃。
内鬼在一个 $n$ 个点 $m$ 条边的简单无向连通图上行走，他从 $1$ 号点出发，目标是 $n$ 号点。
uoj 和 pjudge 分别抓了 $k$ 和 $n-k$ 个壮丁。图上的每个点会恰好分配一个壮丁，负责盘问来往行人。因为人流量不同，一个人经过第 $i$ 个点需要花费的时间是 $t_i$ 。经过一条边的时间可以忽略不计。
uoj 的壮丁很清楚其他 uoj 的壮丁都是鸽子，pjudge 的壮丁也很清楚其他 pjudge 的壮丁都是鸽子，但他们相互不知道对方是不是鸽子。所以，只有当内鬼经过的一条边的两边的壮丁来自同一个 oj 时，他才会被抓住。
你需要构造一个分配壮丁的方案，使得对于任意一条 $1$ 到 $n$ 的最短路，内鬼走这条路都会被抓住。或者判断无解。
输入格式
第一行三个正整数 $n,m,k$ 。
第二行 $n$ 个正整数 $t_1,t_2,\cdots,t_n$ 。
接下来 $m$ 行，每行两个正整数 $u_i,v_i$ ，表示无向图中的一条边。
输出格式
如果存在合法方案，那么输出一个长度为 $n$ 的字符串 $s$ ，其中 $s_i\in \{'P', 'U'\}$ 表示第 $i$ 个点的壮丁是来自 pjudge 还是 uoj 。
否则，输出 impossible 。
样例一
input
3 2 0 1 1 1 1 2 2 3
output
PPP
explanation
uoj 一个壮丁都没有抓到！但是这样就使得每条边的两边的壮丁都来自 pjudge ，因此内鬼走任意一条边都会被抓住。
样例二
input
2 1 1 1 1 1 2
output
impossible
explanation
uoj 和 pjudge 的壮丁互相认为对方会认真盘查，于是自己当鸽子，结果内鬼跑掉了！
样例三
input
8 9 4 3 3 1 2 2 3 2 1 1 2 1 3 1 4 2 5 3 6 4 7 5 8 6 8 7 8
output
PUPUPPUU
样例四、五、六
见下发文件。
数据范围
本题采用子任务捆绑测试。
对于所有数据，保证 $2\le n\le 10^5, 1\le m\le 2\times 10^5, 0\le k\le n, 1\le t_i\le 10^4$ 。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $n\le 15$ | $20$ |
| $2$ | $k=1$ | $30$ |
| $3$ | $u_i\in \{1,n\}$ 或 $v_i\in \{1,n\}$ | $30$ |
| $4$ | $ $ | $20$ |
时间限制：$\texttt{3s}$
空间限制：$\texttt{1024MB}$
提示
UOJ 缺投。