NETADMIN SPOJ (DINIC's Algorithm - Maxflow) solution - JAVA.

Algorithm:

1. Add a sink vertex.
2. Connect each house wishing to connect to the internet (Zi) with the sink with capacity 1
    - directed edge from Zi to sink.
3. For each street, add an undirected edge between the two nodes with capacity that we decide later on.
4. The maximum number of colors that will be necessary is at most the number of houses wanting
    to connect to the internet.
5. The minimum capacity in the graph (of undirected edges) that fills the capacity of directed edges (Zi to sink with cap = 1) is the minimum number of colors required.
6. Use binary search to find out this capacity. Reset graph every time a different capacity is set according to the binary search procedure. Then use Dinic's algorithm to find out the max flow. The max flow must be equal to size(Z) and the capacity of undirected edges should be minimum.


Implementation structure of the graph- 
   
    head[i] - i indexes the ith edges' information.
    the head of this ith edge is indicated by head[i] i. i.e. the "to" value in [from-to]
   
    capacity[i], flow[i] = the capacity and flow of the ith edge
   
    prev[i] = the value i is the index of an edge.
    prev[i] stores the previous(based on insertion order) edge's index i.e. the index
    number used to store information about some previous "outgoing" edge that we recorded
    for the concerned vertex (the vertex from where this edge is originating).
    prev[i] is 0 when no more outgoing edge remains unconsidered for this vertex.
    Every edge's index number i can be used in prev[i] to get index number of the
    previous outgoing edge for the vertex being considered until a -1 is encountered.
   
    top[i] = the index used to store the last "outgoing" edge's index for this vertex i.
    if x == top[i], then we can use prev[x] to get the index of the previous
    (insertion order) outgoing edge from this vertex. This can be done until prev[i]
    returns -1 indicating no more outgoing edges remain unconsidered from this vertex.
   
    work[i] = is a temporary array constructed as a copy of the top[] array after the
    bfs() is done - a level graph has been constructed. It is used during the dfs procedure.
    It ensures that one edge is seen only once during multiple dfs' for a level graph.
    (Remove the assignment in the for loop and you get a TLE)
   
    Q is an array used as a queue
   
Source:

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class NETADMIN {
    static final int INF = 0x7fffffff;
 
    /*
    Structure of the graph- 
    
    head[i] - i indexes the ith edges' information.
    the head of this ith edge is indicated by head[i] i. i.e. the "to" value in [from-to]
    
    capacity[i], flow[i] = the capacity and flow of the ith edge
    
    prev[i] = the value i is the index of an edge.
    prev[i] stores the previous(based on insertion order) edge's index i.e. the index
    number used to store information about some previous "outgoing" edge that we recorded
    for the concerned vertex (the vertex from where this edge is originating). 
    prev[i] is 0 when no more outgoing edge remains unconsidered for this vertex.
    Every edge's index number i can be used in prev[i] to get index number of the
    previous outgoing edge for the vertex being considered until a -1 is encountered.
    
    top[i] = the index used to store the last "outgoing" edge's index for this vertex i. 
    if x == top[i], then we can use prev[x] to get the index of the previous
    (insertion order) outgoing edge from this vertex. This can be done until prev[i] 
    returns -1 indicating no more outgoing edges remain unconsidered from this vertex.
    
    work[i] = is a temporary array constructed as a copy of the top[] array after the 
    bfs() is done - a level graph has been constructed. It is used during the dfs procedure.
    It ensures that one edge is seen only once during multiple dfs' for a level graph.
    (Remove the assignment in the for loop and you get a TLE)
    
    Q is an array used as a queue
    */
    int maxnodes, maxedges, src, dest, edges;
    int[] top, work, Q;
    int[] head, prev, flow, cap, dist;
    
    public void init(int maxnodes, int maxedges){
        this.maxnodes = maxnodes;
        this.maxedges = maxedges;
        top = new int[maxnodes];
        work = new int[maxnodes];
        Q = new int[maxnodes];
        dist = new int[maxnodes];
        
        head = new int[maxedges];
        prev = new int[maxedges];
        
        flow = new int[maxedges];
        cap = new int[maxedges];
        
        clear();
    }
    
    public void clear(){
        Arrays.fill(top, -1);
        edges = 0;
    }
    
    public void addEdge(int u, int v, int capacity){
        head[edges] = v;
        cap[edges] = capacity;
        flow[edges] = 0;
        prev[edges] = top[u];
        top[u] = edges++; 
    }
    
    boolean dinic_bfs(){
        Arrays.fill(dist, -1);
        dist[src] = 0;
        int sizeQ = 0;
        Q[sizeQ++] = src;
        for(int i=0;i<sizeQ;++i){
            int u = Q[i];
            for(int e = top[u]; e>=0; e=prev[e]){
                int v = head[e];
                if(flow[e] < cap[e] && dist[v] < 0){
                    dist[v] = dist[u] + 1;
                    Q[sizeQ++] = v;
                }
            }
        }
        return dist[dest] >= 0;
    }
    
    int dinic_dfs(int u, int f){
        if(u==dest)return f;
        for(int e=work[u]; e>=0;work[u] = e = prev[e]){
            int v = head[e];
            if(flow[e] < cap[e] && dist[v] == dist[u]+1){
                int df = dinic_dfs(v, Math.min(f, cap[e] - flow[e]));
                if(df>0){
                    flow[e] += df; 
                    return df;
                }
            }
        }
        return 0;
    }
    
    public int maxFlow(int src, int dest){
        this.src = src;
        this.dest = dest;
        int flow = 0;
        while(dinic_bfs()){
            System.arraycopy(top, 0, work, 0, maxnodes);
            while(true){
                int df = dinic_dfs(src, INF);
                if(df==0)break;
                flow+=df;
            }
        }
        return flow;
    }
    
    public static void main(String[] args){
        InputReader r = new InputReader(System.in);
        NETADMIN task = new NETADMIN();
        task.init(501, 501*501);
        int nCases = r.nextInt();
        
        while(nCases-->0){
            task.clear();
            int n = r.nextInt();
            int s = 0;
            int t = n;
            int m = r.nextInt();
            int k = r.nextInt();
            
            for(int i=0;i<k;++i){
                int u = r.nextInt()-1;
                task.addEdge(u, t, 1);
            }
            
            for(int i=0;i<m;++i){
                int u = r.nextInt() - 1;
                int v = r.nextInt() - 1;
                task.addEdge(u, v, 1);
                task.addEdge(v, u, 1);
            }
            
            int lo = -1;
            int hi = k;
            while(hi-lo>1){
                int mid = (lo+hi)>>1;
                for(int i =0;i<task.edges; i++){
                    task.flow[i] = 0; 
                    if(task.head[i] != t){
                        task.cap[i] = mid; 
                    }
                }
                int flow = task.maxFlow(s, t);
                if(flow == k )hi = mid;
                else lo = mid;
            }
            System.out.println(hi);
        }
        
        
    }
    
    private static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar, numChars;

        public InputReader(InputStream stream) {
                this.stream = stream;
        }

        private int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }

        private boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}