Semi-Palindromic Tree
Description
Mr. Onsite Problem Investigator, often referred to as O.P.I., felt disheartened when nobody could solve his problem last year. This year, he thought, "I will create a very easy problem that can be solved by everyone". He designed a straightforward problem and submitted it to the contest coordinators. To his surprise, it was rejected for being overly simplistic, and he was even labeled "lazy" for his efforts. O.P.I. got very angry, and he crafted an even more straightforward problem. However, he cleverly disguised it to appear as the most complex problem ever.
The problem goes as follows:
Given a tree, you need to assign a character to each node. Your tree must satisfy two conditions:
- The string formed by traversing from one leaf node to another must create a palindrome.
- The string formed by traversing from a leaf node to a non-leaf node must not result in a palindrome.
So can you solve the hardest problem ever?
The first line contains an integer $n$ $(1 \leq n \leq 2 \times 10^5)$ — the number of vertices in the tree.
The next $n - 1$ lines each contain two integers $u$ and $v$ $(1 \leq u, v \leq n, u \neq v)$ denoting an edge connecting vertex $u$ and vertex $v$. It is guaranteed that the given graph is a tree.
If it is impossible to assign characters while satisfying the conditions or if you require more than $26$ characters, print $-1$. Otherwise, print a sequence of $n$ lowercase English characters, where the $i$-th character represents the character assigned to node $i$. If there are multiple solutions, print the lexicographically smallest answer.
Input
The first line contains an integer $n$ $(1 \leq n \leq 2 \times 10^5)$ — the number of vertices in the tree.
The next $n - 1$ lines each contain two integers $u$ and $v$ $(1 \leq u, v \leq n, u \neq v)$ denoting an edge connecting vertex $u$ and vertex $v$. It is guaranteed that the given graph is a tree.
Output
If it is impossible to assign characters while satisfying the conditions or if you require more than $26$ characters, print $-1$. Otherwise, print a sequence of $n$ lowercase English characters, where the $i$-th character represents the character assigned to node $i$. If there are multiple solutions, print the lexicographically smallest answer.
5
1 2
2 3
3 4
4 5
abbba