For the first subtask, it suffices to generate all strings of length ~N~ and check if they will form the given graph.

Time complexity: ~\mathcal{O}(N^2 26^N)~

The second subtask is just a simpler case of the full solution. To solve it we must make an observation about this graph.
Let ~a(n)~ be the set of neighbours of node ~n~. Let ~b(n) = a(n) \cup n~. Then we have that if for two nodes ~i~ and ~j~ that ~S_i = S_j~ then ~b(i) = b(j)~. Therefore, we can generate ~b(i)~ for each of the nodes in the graph and we will know which characters are equal.

Since the graph is a tree, we observe that none of the ~b(i)~ will be equal so each node must represent a distinct character with the exception of a connected component consisting of exactly ~2~ nodes. We observe that in this special case, the two nodes can be assigned the same letter. It follows that there can be no more than ~25~ nodes in the input otherwise the answer is just -1. Additionally, observe that each node can only be adjacent to at most ~2~ other nodes since each character in the alphabet is adjacent to exactly ~2~ other letters. Combining these observations, we realize that the graph will be composed of a single chain which we can perform depth first search on to assign letters.

Time complexity: ~\mathcal{O}(M\log(26)+N)~

For the final subtask, we will generalize the observation from subtask 2. Observe that if two nodes have ~b(i) = b(j)~, it is always optimal to assign ~S_i = S_j~ as we take up less characters in the alphabet. After calculating ~b(i)~ for all the nodes, we try to assign an id to each distinct ~b(i)~. If there are more than ~26~ such groups, then the answer is -1 since there are only ~26~ letters in the alphabet. After this is done, we compress all nodes in the graph that have the same ~b(i)~ into one node while maintaining the edges between nodes. The resulting compressed graph has at most ~26~ nodes that represent a group of nodes that should be assigned the same letter. Observe that the compressed graph must satisfy certain properties we defined in subtask 2. Once again, the degree of each node must not be greater than ~2~ which means that the graph is a series of chains or rings. The only case that is different from subtask 2 is that it is possible to have a ring consisting of all ~26~ letters but any smaller ring would be invalid. Taking this special case in mind, we can perform the same procedure and perform a depth first search on each component to assign letters.

Time complexity: ~\mathcal{O}(M\log(26)+N)~