该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

$TooY0ung$ 发明了一款小游戏，名为 " $TooY0ung$ 的诅咒"，$TooY0ung$ 将你扔入了一个深渊（可以理解为山谷），你需要自己爬出山谷。

题目描述

$TooY0ung$ 把你丢到了一个编号为 $s$ 的落脚点，并给你了一张记录了附近所有落脚点以及它们连通关系的地图。

$TooY0ung$ 希望你能寻找到一条独自爬出深渊的路径。地图上有 $n$ 个落脚点，编号为 $1$ ~ $n$（$s$ 一定在其中），每个落脚点的深度为 $d_i$，作为萌新冒险者要尽量避免去深度较大的落脚点才有更大的几率生存下来。

一条路径中（包括两边的端点）所有落脚点深度最大的落脚点的深度，就是这条路径的深度。

现在，需要你找到一条深度最小的路径，通往深渊的出口（深度为 $0$ 的落脚点，可能有多个或零个），但是良心的 $TooY0ung$ 并不关心路径的样子，他只想知道路径的深度是多少。

输入格式

第一行按顺序输入三个数字，$n$ 表示落脚点的个数，$m$ 表示无向边的个数，$s$ 表示起始落脚点的位置。

第二行输入 $n$ 个正整数 $d_i$，分别表示 $i$ 个落脚点的深度。

接下来的 $m$ 行，每行两个正整数 $u$ 和 $v$，表示落脚点 $u$ 和 落脚点 $v$ 之间存在一条双向边。

输出格式

输出一个正整数，表示路径的深度。

如果不存在这样的路径，则输出 "GG"，输出不含引号。

5 5 1
1 2 4 3 0
1 2
2 3
3 4
2 4
4 5

3

5 5 1
1 2 3 4 5
1 2
2 3
3 4
2 4
4 5

GG

样例1解释

深度最小的路径之一是$1$ -> $2$ -> $4$ -> $5$，它的深度是 $3$，还有一条深度也是 $3$ 的路径，$1$ -> $2$ -> $4$ -> $2$ -> $4$ -> $5$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le s,u,v \le n \le 1000$，$1 \le m \le 2000$，$0 \le d_i \le 10^7$。

地图可能是存在自环或重复边的无向有环图。