题目描述

小 B 喜欢图，尤其是边数不太多的无向简单图。

母亲节快到了，小 B 在纸上画了一张有 $n$ 个节点、$m$ 条边的无向简单图（即，不存在重边、自环），保证每个点只和最多 $7$ 个点相邻。接着，他想用 $4$ 种不同的颜色给图中的节点进行染色，作为妈妈的母亲节礼物送给她。

小 B 希望染色之后的图尽量漂亮，他觉得相同颜色的点连成一片不好看。所以，他希望能给每对相邻的节点染上不同的颜色。遗憾的是，小 B 很快发现，在有些图中，这是不可能做到的。他不得不降低要求：每个点相邻的点中，至多有一个点和它的颜色相同。

限制条件放松了，问题也就变得简单了；但是小 B 忙着做大作业，所以来找你帮忙。现在，请你告诉小 B，是否能给图中每个点染上一个恰当的颜色，恰好满足小 B 的要求？如果可以，请你给他指出一种染色方案；否则，只好残忍地告诉小 B：impossible。

输入格式

输入有多组数据，第一行一个整数 $T$（$1\le T\le 10$） ，表示数据组数。

对于每组数据：

第一行两个整数 $n,m$（$1\le n\le 25000,1\le m\le 10^5$），分别表示图的点数和边数（约定点从 $1$ 开始标号）。

接下来 $m$ 行，每行两个整数 $x,y$（$1\le x,y\le n$），描述图中的一条边，保证不存在重边、自环。

保证在一个输入文件中，有 $\sum n\le 200000,\sum m\le 800000$。

输出格式

我们用小写英文字母 a、b、c、d 给四种不同的颜色标号。

对于每组数据：

• 如果有解，输出一行一个长度为 $n$ 的字符串 $S$，其中 $S_i$ 表示你给第 $i$ 个点染上的颜色（下标从 $1$ 开始）；
• 否则，输出 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

提示

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。