## 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.