Disable the Alien Warp Escape

An alien spaceship is trying to escape using a network of warp points on a plane. There are n warp points with coordinates \( (x_i,y_i) \) for \( i=1,2,\ldots,n \). Additionally, there are m bidirectional space tunnels connecting some pairs of warp points. The \( i\)th tunnel connects warp point \( u_i \) and \( v_i \) and requires \( w_i \) units of energy to activate. It is guaranteed that for any two tunnels \( i \) and \( j \), the line segments connecting \( (x_{u_i},y_{u_i}) \) with \( (x_{v_i},y_{v_i}) \) and \( (x_{u_j},y_{u_j}) \) with \( (x_{v_j},y_{v_j}) \) do not intersect, and there are no two tunnels connecting the same pair of endpoints simultaneously.

The alien technology is astonishing: to perform a warp, the aliens must visit every warp point at least once (they may start and end at any warp point), and the total energy consumed is defined as the bitwise OR of the activation energies of all tunnels used along the path (repeated use of a tunnel only counts once). The spaceship has an energy reserve of x units. Thus, if there exists any route whose total energy (bitwise OR of the used tunnels' activation energies) is at most \( x \), the aliens can escape.

You, however, are tasked with preventing the alien escape. To do so, you are allowed to modify the activation energy required by any tunnel through a series of operations. In each operation you may:

• Choose any tunnel connecting warp points \( u \) and \( v \) (it is guaranteed that such a tunnel exists).
• Increase its activation energy by an integer \( d \) (with \( d \ge 0 \)) such that the new activation energy does not exceed \( 2^{31}-1 \). That is, if the current activation energy is \( w \), it becomes \( w+d \).

The cost of an operation is the number of 1's in the binary representation of \( d \) (i.e. __builtin_popcount(d) in C++). You may perform as many operations as you wish, possibly on different tunnels. Note that if an edge is used several times in the aliens' path, you only need to activate it once.

The aliens can only complete their escape if there is a route (covering all warp points at least once) using tunnels whose total activation energy (computed by bitwise OR) is at most \( x \). Notice that for the total energy of a route to be at most \( x \), every tunnel used must have all its 1-bits coming from \( x \); in other words, for an edge with activation energy \( w \) to be usable, it must satisfy

[ w ; & ; \sim x = 0.]

Your goal is to design an operation plan with minimum total cost such that after your modifications there is no route (covering every warp point) whose total activation energy is at most \( x \).

---

Problem Restatement

We have a graph with n nodes and m edges. Each edge has an initial weight \( w_i \). An edge is usable by the aliens if \( w_i \) only has 1's in positions where \( x \) (given in the input) has 1's (i.e. \( w_i \; \& \; \sim x = 0 \)). The aliens win if there exists a connected subgraph spanning all nodes composed entirely of usable edges. You can "disable" an edge by increasing its weight. For any edge you choose to modify, you can add an integer \( d \) (at cost equal to the popcount of \( d \)) so that its new weight \( w_i+d \) is no longer usable (i.e. it has at least one bit that is not set in \( x \)).

You need to choose a set of edges (and suitable \( d \) for each, with minimum individual cost of 1 per edge modification being always achievable by choosing an appropriate power of 2) to modify so that in the resulting graph, the subgraph of usable edges is disconnected. In other words, you want to remove a set of edges from the usable subgraph such that no spanning tree exists, while minimizing the sum of the costs (popcounts) of the chosen modifications.

Simplification: Since the minimum cost to disable any eligible edge is 1, the problem reduces to finding the minimum number of edges that must be "disabled" (modified) in the current usable subgraph in order to disconnect it. If the usable subgraph is already disconnected, the minimum cost is 0.

This is equivalent to computing the global edge connectivity (minimum cut) of the usable subgraph. Output that minimum cost.

inputFormat

The first line contains three integers \( n \), \( m \), and \( x \) (number of warp points, number of tunnels, and available energy, respectively).

The next \( n \) lines each contain two integers \( x_i \) and \( y_i \), representing the coordinates of warp point \( i \).

The following \( m \) lines each contain three integers \( u_i \), \( v_i \), and \( w_i \), describing a tunnel between warp points \( u_i \) and \( v_i \) with activation energy \( w_i \). The warp points are numbered from 1 to \( n \).

outputFormat

Output a single integer: the minimum total cost of operations needed so that there is no route (covering all warp points) with a total activation energy (bitwise OR of used tunnels) at most \( x \).

sample

3 2 1
0 0
1 0
0 1
1 2 1
2 3 1

1

</p>