(Analysis by Dhruv Rohatgi )

In this problem, we have a graph where the vertices are pastures, and there is an edge between two pastures if those two pastures are the favorites of some cow. We want to color each vertex with one of 4 colors so that no two adjacent vertices (i.e. no two vertices connected by an edge) are given the same color.

So let's just assign colors to the vertices in order. For each vertex, we need to find a color which has not already been assigned to any adjacent vertices. Luckily, in our case this is always possible: the problem statement guarantees that no vertex is adjacent to more than 3 other vertices, so at least one of the 4 colors is free. Thus, we will always be able to find a coloring with this strategy. The complexity is O(NM) if implemented naively, and could easily be reduced to O(N) by storing for each vertex the identities of the ≤3 adjacent vertices. However, for the given constraints, this optimization is unnecessary.