Maximizing Network Safety Coefficient

Aiden owns a computer network where every computer is equipped with monstrous hardware (each at least equipped with an Intel Xeon E50 v40 + 40 GTX10800Titan cards) and all computers are connected directly or indirectly via wireless links. This network can be represented as an undirected connected graph \(G=(V,E)\). However, the network is not secure enough: dedsec may attack the network by cutting some wireless connections and thereby disconnecting it.

To avoid a complete network failure, Aiden decides to designate some computers as computing nodes (denoted by \(V_1\)) while the remaining computers serve as relay nodes (denoted by \(V_2\)). Each computer has a different work capability denoted by \(w_i\). The overall work capability of the network is defined as \(W=\sum_{v\in V_1}w_v\). In order to fulfill a required work capability, the chosen computing nodes must satisfy \(W\ge R\) (where \(R\) is given).

The safety coefficient \(k\) of the network is defined as the maximum integer such that for any two distinct computing nodes \(u,v\in V_1\), there exist at least \(k\) edge-disjoint paths (paths that do not share any edge, though they may share vertices) between \(u\) and \(v\) in the entire graph \(G\).

Your task is to decide the safety coefficient of Aiden’s network under the following rules:

1. You are given a connected undirected graph with \(n\) nodes and \(m\) edges.
2. Each node has an integer work capability \(w_i\).
3. You are given a label for each node: if the label is 1, the node is a candidate to be a computing node (\(V_1\)); if the label is 2, it will be a relay node (\(V_2\)).
4. It is required that the total work capability of the computing nodes is at least \(R\). If \(\sum_{v\in V_1} w_v < R\), output \(-1\).
5. If the number of computing nodes is less than 2, output \(0\) (since safety coefficient is defined over pairs).
6. Otherwise, compute the safety coefficient \(k\) as the minimum, over all pairs of distinct computing nodes, of the maximum number of edge-disjoint paths between them (each edge has unit capacity).

Input/Output details: See below.

inputFormat

The first line contains three integers \(n\), \(m\), and \(R\) \( (1\le n\le ? ,\; 1\le m\le ? ,\; R\ge 0)\) representing the number of nodes, the number of edges, and the required total work capability for computing nodes respectively.

The second line contains \(n\) integers \(w_1, w_2, \ldots, w_n\), where \(w_i\) is the work capability of node \(i\).

The third line contains \(n\) integers, each either 1 or 2. A value of 1 means node \(i\) is a computing node candidate (\(V_1\)), and 2 means it is a relay node (\(V_2\)).

Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating an undirected edge between node \(u\) and node \(v\). Nodes are numbered from 1 to \(n\). It is guaranteed that the graph is connected.

outputFormat

If the total work capability of the computing nodes (i.e. nodes labeled 1) is less than \(R\), output \(-1\). If there is only one or no computing node, output \(0\). Otherwise, output a single integer representing the safety coefficient \(k\) of the network, defined as the minimum number of edge-disjoint paths between any two distinct computing nodes.

sample

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

2