## DMOPC '19 Contest 1 P4 - A Strange Graph

View as PDF

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Bob was bored so he decided to write down a string that consists of lowercase letters. He then decided to build a graph that represented the string. The graph has nodes and the -th node contains the character . 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.

#### Constraints

The graph is guaranteed to be connected.

#### Input Specification

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

#### Output Specification

Output any string consisting of 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

dccb

#### Explanation for Sample Input 1

Many others 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 Input 2

-1

#### Explanation for Sample Input 2

No such string exists.