Educational Codeforces Round #105 A-Z Graph - Graphs + Construction
Solution:
It is obvious if the vertices can be repeated.
Assuming there is a solution, there must be two edges v1->v2 and v2->v1.
If k is an odd number, then we can give this way: v1->v2->v1->v2->v1. And the back way is v1->v2->v1->v2->v1. It's the same way! So no matter what characters in v1->v2 and v2->v1 are.
If k is an even number, it's a little bit complex. For example, k=4. Assuming there is a solution, and the solution is: v1->v2->v3->v4. So the back way is: v4->v3->v2->v1. And the string is the same.
So we can found that v2->v3 and v3->v2 must be the same!
So string of v2->v3->v2->v3 must be same with string of v3->v2->v3->v2.
In summary, for k is an odd number, we find two vertices that can be directly connected. If k is an even number, find two vertices that can be directly connected and have the same letter.