DMOPC '19 Contest 1 P4 - A Strange Graph

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.8s
Memory limit: 256M

Problem type

Bob was bored so he decided to write down a string S that consists of N lowercase letters. He then decided to build a graph that represented the string. The graph has N nodes and the i-th node contains the character S_i. Two distinct nodes are connected by a bidirectional edge if the characters written on these two nodes are either equal or adjacent. Two characters are adjacent if they appear next to each other in the alphabet. Note that the alphabet is considered cyclic so a and z are adjacent. Bob has given you this graph and challenges you to find any string that would generate this graph or determine that Bob has made an error somewhere.

The given graph will be simple and won't have self edges.


1 \le N \le 100\,000
0 \le M \le \min(1\,000\,000, \frac{N(N-1)}{2})

Subtask 1 [5%]

1 \le N \le 5

Subtask 2 [10%]

M = N-1
The graph is guaranteed to be connected.

Subtask 3 [85%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, N M, representing the number of nodes and number of edges in the graph.
The next M lines contain two space-separated integers, x_i y_i, representing a bidirectional edge connected vertices x_i and y_i.

Output Specification

Output any string S consisting of N lowercase letters that would generate the given graph or -1 if no such string exists.

Sample Input 1

4 5
1 2
1 3
3 2
4 2
3 4

Sample Output 1


Explanation for Sample Output 1

Many other answers are possible, including abbc and yzza.

Sample Input 2

5 6
1 2
1 3
3 4
4 2
4 5
1 4

Sample Output 2


Explanation for Sample Output 2

No such string exists.


There are no comments at the moment.