题目描述

众所周知，Berland 由偶数座城市组成，城市之间由双向道路连接，并且从任意一座城市都可以通过道路到达任意另一座城市。

任意两座城市之间至多有一条直接道路，也不存在一条道路连接某座城市和它自己。

由于矛盾不断加剧，Berland 决定不再作为一个单一国家存在，而是成立 Berland 联盟，并把所有城市划分成若干个国家。

一个合法的划分必须满足以下两个条件：

1. 每个国家至少包含两座城市；
2. 对于同一个国家中的任意两座城市，只使用该国家内部城市和道路时，它们之间恰好存在一条路径。

换句话说，每个国家所包含的城市在原图中的诱导子图必须是一棵树。

请构造任意一种满足要求的划分方案。

你不需要最小化国家数量。

输入格式

第一行一个整数 $tst$，表示测试用例数量。

对于每组测试数据：

• 第一行两个整数 $n,m$，分别表示城市数和道路数；
• 接下来 $m$ 行，每行两个整数 $a,b$，表示城市 $a$ 和城市 $b$ 之间有一条双向道路。

保证：

• $1\le tst\le 50$；
• $2\le n\le 100$；
• $n$ 为偶数；
• $1\le m\le 1000$；
• $1\le a<b\le n$；
• 图为简单连通无向图；
• 所有测试用例的城市总数不超过 $100$；
• 所有测试用例的道路总数不超过 $1000$。

输出格式

对于每组测试数据输出一行，共 $n$ 个整数。

第 $i$ 个整数表示第 $i$ 座城市所属国家的编号。

如果一共划分出了 $k$ 个国家，则国家编号必须恰好为 $1,2,\ldots,k$。

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

样例

2
4 3
1 2
2 3
1 4
4 4
1 2
2 3
1 4
1 3

1 1 1 1
1 2 2 1