G. 国际象棋聚会（）

题目描述

国际象棋城中有 $n$ 位朋友和 $n$ 栋房屋，它们都从 $1$ 到 $n$ 编号。朋友 $i$ 居住在房屋 $i$ 中。

城市中有 $m$ 条双向道路连接这些房屋，所有房屋构成一个连通网络。

城市中还有 $n$ 个虚拟国际象棋俱乐部，编号为 $1$ 到 $n$。每位朋友必须恰好选择一个俱乐部加入。不同朋友可以加入同一个俱乐部，也允许某些俱乐部没有成员。

当朋友 $i$ 举办国际象棋聚会时，所有满足下列条件的朋友都会参加：

• 与朋友 $i$ 属于同一个俱乐部；
• 其房屋与房屋 $i$ 之间有一条道路直接相连。

聚会人数还包括朋友 $i$ 本人。

如果聚会的总人数为偶数，那么这场聚会就是成功的，因为所有人都可以同时两两对弈。

请为每位朋友选择一个俱乐部，使每位朋友举办的聚会都成功；如果不存在这样的分配方案，则报告无解。

输入格式

本题包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

每组测试数据的第一行包含两个整数 $n,m$，分别表示房屋数量和道路数量。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示房屋 $u$ 与房屋 $v$ 之间有一条双向道路。

保证：

• $u\ne v$；
• 任意两栋房屋之间至多有一条道路；
• 整张图连通。

输出格式

对于每组测试数据：

• 如果不存在合法的俱乐部分配方案，输出一行 -1；
• 否则输出 $n$ 个整数 $c_1,c_2,\ldots,c_n$，其中 $c_i$ 表示朋友 $i$ 加入的俱乐部编号。

如果有多种合法方案，输出任意一种即可。

数据范围

所有测试数据中：

样例

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

1 1
-1
3 3 6 6 6 2 6 2