Description

The citizens of a small village are tired of being the only inhabitants around without a connection to the Internet. After nominating the future network administrator, his house was connected to the global network. All users that want to have access to the Internet must be connected directly to the admin's house by a single cable (every cable may run underground along streets only, from the admin's house to the user's house). Since the newly appointed administrator wants to have everything under control, he demands that cables of different colors should be used. Moreover, to make troubleshooting easier, he requires that no two cables of the same color go along one stretch of street.

Your goal is to find the minimum number of cable colors that must be used in order to connect every willing person to the Internet.

Input

t [the number of test cases, t<=500]
n m k [n <=500 the number of houses (the index of the admin's house is 1)]
[m the number of streets,k the number of houses to connect]
h1h2 ...hk [a list ofk houses wanting to be conected to the network, 2<=hi<=n]
[The next m lines contain pairs of house numbers describing street ends]
e11e12
e21e22
...
em1em2
[next cases]

Output

For each test case print the minimal number of cable colors necessary to make all the required connections.

Example

Input:
2
5 5 4
2 3 4 5
1 2
1 3
2 3
2 4
3 5
8 8 3
4 5 7
1 2
1 8
8 7
1 3
3 6
3 2
2 4
2 5

Output:
2
1

Illustration to the first example


题意：一座村庄有 N 户人家。只有第一家可以连上互联网，其他人家要想上网必须拉一根缆线通过若干条街道连到第一家。每一根完整的缆线只能有一种颜色。网管有一个要求， 各条街道内不同人家的缆线必须不同色， 且总的不同颜色种数最小。求在指定的 K 户人家都能上网的前提下，最小的不同颜色种数。 （1 <= N <= 500）

摘自网络流建模汇总的分析：此题乍一看不太好考虑，不知道如何去控制同一街道内的缆线颜色各不相同。我们不妨先尝试着建立一个网络模型出来：以第一家作为汇点 t，K 户人家中的每一户 i 作为一个点并连边(s, i, 1)，对每条街道(u, v)，连边(u, v, c), (v, u, c)，c=∞。这样求完最大流后每一条 s-t 流均对应一户人家的缆线，而各条街道内的流量表示有多少户人家的缆线同时穿过该街道， 那么这个流量就是只考虑该条街道的时候最少的不同颜色种数。 那么答案是否就是所有街道的不同颜色种数的最大值呢？当然不是！最大流只保证总流量最大，而不会去管每条流具体该往哪儿流，所以这么做不一定能得到最优解。 我们只要稍微修改这个模型就一定能保证得到最优解：强制 c 等于某个值 limit，再对网络求最大流，如果等于 K，说明用 c 种不同的颜色已经足够了；如果小于 K，说明 c 种还不够，还需要往高了调。同时此处的单调性也很明显：c 越高越容易满足要求。思路一下就豁然开朗了：二分 c 的值，如果足够了就往下调，否则往上调，直到找到足够和不足够的临界值为止。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxm = 1000010;
const int inf = 0x3f3f3f3f;
struct G
{
    int v, cap, next;
    G() {}
    G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化，qw队列
void init()
{
    memset(p, -1, sizeof(p));
    T = 0;
}
void add(int u, int v, int cap)
{
    E[T] = G(v, cap, p[u]);
    p[u] = T++;
    E[T] = G(u, 0, p[v]);
    p[v] = T++;
}
bool bfs(int st, int en, int n)
{
    int i, u, v, head, tail;
    for(i = 0; i <= n; i++) d[i] = -1;
    head = tail = 0;
    d[st] = 0;
    qw[tail] = st;
    while(head <= tail)
    {
        u = qw[head++];
        for(i = p[u]; i + 1; i = E[i].next)
        {
            v = E[i].v;
            if(d[v] == -1 && E[i].cap > 0)
            {
                d[v] = d[u] + 1;
                qw[++tail] = v;
            }
        }
    }
    return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
    if(u == en || f == 0) return f;
    int flow = 0, temp;
    for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
    {
        G& e = E[temp_p[u]];
        if(d[u] + 1 == d[e.v])
        {
            temp = dfs(e.v, en, min(f, e.cap));
            if(temp > 0)
            {
                e.cap -= temp;
                E[temp_p[u] ^ 1].cap += temp;
                flow += temp;
                f -= temp;
                if(f == 0)  break;
            }
        }
    }
    return flow;
}
int dinic(int st, int en, int n)
{
    int i, ans = 0;
    while(bfs(st, en, n))
    {
        for(i = 0; i <= n; i++) temp_p[i] = p[i];
        ans += dfs(st, en, inf);
    }
    return ans;
}
int a[maxn];
struct Street{
    int st,en;
}street[maxm];
int main(){
    int T,n,m,k;
    scanf("%d", &T);
    while(T--){
        scanf("%d %d %d", &n,&m,&k);
        for(int i=1; i<=k; i++) scanf("%d", &a[i]);
        for(int i=1; i<=m; i++) scanf("%d %d", &street[i].st, &street[i].en);
        int st = 0, en = 1;
        int l = 0, r = n, ans;
        while(l<=r){
            int mid = (l+r)/2;
            init();
            for(int i=1; i<=k; i++) add(st, a[i], 1);
            for(int i=1; i<=m; i++){
                add(street[i].st, street[i].en, mid);
                add(street[i].en, street[i].st, mid);
            }
            int temp = dinic(st, en, n+1);
            if(temp == k){
                ans = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}