Description

Xiao B likes graphs, especially undirected simple graphs with not too many edges.

Mother’s Day is coming. Xiao B drew on paper an undirected simple graph with $n$ nodes and $m$ edges (that is, there are no multiple edges or self-loops). It is guaranteed that each node is adjacent to at most $7$ other nodes. Then, he wants to color the nodes of the graph using $4$ different colors as a Mother’s Day gift for his mom.

Xiao B wants the colored graph to look as nice as possible. He thinks it looks bad when nodes of the same color are connected together. So, he hopes to color every pair of adjacent nodes with different colors. Unfortunately, Xiao B soon found that in some graphs, this is impossible. He had to lower his requirement: among the neighbors of each node, there are at most one node that has the same color as it.

With the relaxed constraints, the problem becomes easier. But Xiao B is busy with homework, so he asks you for help. Now, please tell Xiao B whether it is possible to assign a proper color to every node, satisfying Xiao B’s requirement exactly. If it is possible, output one coloring scheme; otherwise, tell Xiao B cruelly: impossible.

Input Format

There are multiple test cases. The first line contains an integer $T$ ($1\le T\le 10$), indicating the number of test cases.

For each test case:

The first line contains two integers $n,m$ ($1\le n\le 25000,1\le m\le 10^5$), denoting the number of nodes and edges in the graph (nodes are numbered starting from $1$).

The next $m$ lines each contain two integers $x,y$ ($1\le x,y\le n$), describing an edge of the graph. It is guaranteed that there are no multiple edges or self-loops.

It is guaranteed that, in one input file, $\sum n\le 200000$ and $\sum m\le 800000$.

Output Format

We use lowercase English letters a, b, c, d to label the four different colors.

For each test case:

• If a solution exists, output one line with a string $S$ of length $n$, where $S_i$ denotes the color assigned to node $i$ (index starting from $1$).
• Otherwise, output impossible.

1
8 28
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8

abcdabcd

Hint

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017.

Translated by ChatGPT 5