K. KitKat Kit
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a kindergarten in the kingdom of Kinderland, kids compete in the Imperial Chocolate Pioneers Championship. Unlike that stupid programming contest with Choco Pies as prizes, this championship awards KitKat kits.

After the contest, each of the $$$n$$$ kids receives a kit. The kid who finishes in $$$i$$$-th place gets $$$k_i$$$ chocolate bars, where $$$k_i$$$ is a positive integer. Kids with better results must receive more chocolate bars, and every kid must receive at least one bar. Thus, the kit sizes must satisfy $$$k_1 \gt k_2 \gt \cdots \gt k_n \gt 0$$$.

The jury knows of $$$m$$$ distinct groups of three friends who will compare their prizes after the award ceremony. A kid may belong to more than one group. The jury considers the distribution fair if, in each group, the largest kit contains fewer bars than the other two kits combined. Thus, for a group of friends in places $$$a \lt b \lt c$$$, the kit sizes must satisfy $$$k_a \lt k_b + k_c$$$.

Taxes on prizes in Kinderland depend on the size of the largest prize. Help the jury find a fair distribution for which $$$k_1$$$ is as small as possible. It can be shown that a fair distribution always exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$, denoting the number of kids and the number of groups of friends ($$$3 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$).

Each of the following $$$m$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$c$$$, denoting the places of the three friends in a group ($$$1 \le a \lt b \lt c \le n$$$). All triples $$$(a, b, c)$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ integers $$$k_1, k_2, \ldots, k_n$$$, where the kid in $$$i$$$-th place receives $$$k_i$$$ chocolate bars ($$$k_1 \gt k_2 \gt \cdots \gt k_n \gt 0$$$). The distribution must satisfy $$$k_a \lt k_b + k_c$$$ for every given group $$$(a, b, c)$$$. Among all distributions satisfying these conditions, $$$k_1$$$ must be as small as possible.

If there are multiple answers, print any of them.

Example
Input
2
3 1
1 2 3
11 5
1 4 5
2 7 8
3 6 9
5 6 7
8 9 10
Output
4 3 2
13 12 11 10 9 8 7 6 4 3 1