Unmanned Aerial Vehicles (UAVs), commonly known as drones, are starting to be used for high resolution and 3D mapping1 . A group of ecologists have decided to use a (small) UAV to map out their study area, down to every tree. Unfortunately, it is hard to tell from the resulting image data the total number of species of trees in the area since many look similar.2 Suppose there are n trees in the area and let us assume for simplicity that there are only two different species, say Acacia and Bactris. Believe it or not, it is very hard to tell by looking at a tree by itself which kind it is. However, it is much easier to tell whether two trees are the same species or not. So the scientists do the following. For each pair of 3D tree images i and j the scientists look at them side by side and decide whether they are the same species or different. They also have the option of not giving an opinion and just leave the pair without a decision. So now the scientists have the collection of n trees, as well as a collection of m decisions (either same or different) for the pairs for which some decision was made. They would like to know whether this data is self-consistent. That is, we will say that m decisions are consistent if it is possible to reliably label each tree either Acacia or Bactris in such a way that for each same pair (i, j) the trees i and j indeed have the same label, while for each different pair (i, j) the trees i and j have different labels. Give an algorithm with running time O(m+n) that determines whether the m decisions are consistent. Dont forget to prove its correctness and termination. Note that the input consists of the number of trees, n, and a list of m decisions for some pairs of trees. For example, n = 4, and (1, 2) same, (1, 3) different, (2, 4) same. Extra Credit: Will your algorithm work if there are more than two species, say three (with Cecropia)? If it does, give a proof of correctness. If not, give a counter-example.