6002：Game Leader

Recently Tom is playing an interesting game. The game contains a social network, so players can make friends with each other. The friend relation is symmetric, which means if A is a friend of B, B is also a friend of A.
Players’ ratings are distinct from each other, which means there are no two players sharing a same rating. Each player owns a ranklist containing all his friends’ rating (including himself) and there is one leader who has the highest rating in each player’s ranklist.
Tom has N friends. During the communications with these friends, he knows some pairs of friends are also friends. But he doesn’t know all the such pairs. In other words, some friends maybe are friends but Tom doesn’t know it.
One day, Tom noticed that the system started showing the number of leaders for every friend.
E.g. the system may says Peter is leader on 3 players’ ranklist.
Now Tom can see the number of leaders for every friend. He would like to know the least number of strangers’ ranklist leader are his friends.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line consists of 3 integers, N, M and R representing the number of people on Tom’s ranklist(including Tom), the number of friendships Tom knows and the rank of Tom in his ranklist(1-indexed). The next line consists of N integers, the $i^{th}$ integer $C_i$ represents the number of leaders for the friend on rank i. The following M lines each consists of 2 integers $X_i$ , $Y_i$ , means that the friend on rank $X_i$ is a friend of friend on rank $Y_i$.

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the least number of ranklists that not owned by Tom’s friend but the leader is Tom’s friend.

limits

$\bullet 1 ≤ T ≤ 100.$
$\bullet 1 ≤ N, M ≤ 10^5.$
$\bullet 1 ≤ X_i ≤ N.$
$\bullet 1 ≤ Y_i ≤ N.$
$\bullet 1 ≤ R ≤ N.$
$\bullet R \neq X_i .$
$\bullet R \neq Y_i .$
$\bullet X_i \neq Y_i .$
$\bullet 0 ≤ C_i ≤ 10^9.$
$\bullet$ It’s guaranteed that the data is valid.