Public Judge

pjudge

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21694. 【NOIP Round #3】抓内鬼

统计

题目描述

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 缺投。