#P7428. [THUPC2017] 母亲节的礼物

[THUPC2017] 母亲节的礼物

题目描述

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

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

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

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

输入格式

输入有多组数据,第一行一个整数 TT1T101\le T\le 10) ,表示数据组数。

对于每组数据:

第一行两个整数 n,mn,m1n25000,1m1051\le n\le 25000,1\le m\le 10^5),分别表示图的点数和边数(约定点从 11 开始标号)。

接下来 mm 行,每行两个整数 x,yx,y1x,yn1\le x,y\le n),描述图中的一条边,保证不存在重边、自环。

保证在一个输入文件中,有 n200000,m800000\sum n\le 200000,\sum m\le 800000

输出格式

我们用小写英文字母 abcd 给四种不同的颜色标号。

对于每组数据:

  • 如果有解,输出一行一个长度为 nn 的字符串 SS,其中 SiS_i 表示你给第 ii 个点染上的颜色(下标从 11 开始);
  • 否则,输出 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。