As you have probably noticed, the problem can be described in the language of graphs. Vertices of the graph are friends, the edges correspond to the "can choose as the Happy number" relation. Our goal is to pick some of the edges so that the resulting graph is connected, while trying to minimize a quantity H related to the distribution of the edges with respect to the vertices (H is the number of Happy Packs). Obviously, as long as the marked edges form a cycle, we can remove at least one of them and H will remain the same or even decrease. Thus, without loss of generality, we can search for an optimal solution in which the chosen edges form a spanning tree.
Every spanning tree has the same number of edges, (N-1), so there is an obvious lower bound on the value of H: H ≥ ceil((N-1)/K), where ceil(X) denotes the least integer greater or equal to X.
The case K=1 is the simplest one, as the lower bound can be attained trivially by choosing any spanning tree in the graph. This can be done by performing a depth-first search on the tree, for example.
The case K=2 is only slightly more complicated. Again, the lower bound can be attained by choosing any spanning tree and partitioning it into a set of edge-pairs (and, in the case of N even, one unpaired edge). This partitioning can be performed recursively and fits well into the depth-first search for the spanning tree.
The algorithm partitions the edges of a tree T with root v and a "dangling edge" e which connects it to the rest of the whole spanning tree. If the number of the edges in tree T was odd, the dangling edge will be used in the pairing as well, otherwise it'll be left untouched.
At the beginning, the algorithm processes all the subtrees of tree T. The subtrees with odd number of edges get partitioned completely, using up their respective dangling edges. The dangling edges of the other subtrees are free so far, so we can pair them up arbitrarily. If there was an odd number of them, we pair the dangling edge e of tree T to one of them. Once we process the whole graph, we'll have partitioning of all the edges of the spanning tree.
The only remaining case present in the hard input was K=3. This case is the most difficult one and we are not aware of any solution better than an exhaustive search (in fact, a generalization of this problem is provably NP-complete). Due to the size of such test cases, solving them by hand was most likely a simpler option.