Doludu and baluteshih are playing a game. The rules are simple: there is a connected undirected graph $$$G$$$ with $$$N$$$ vertices and $$$M$$$ edges. Each edge is painted with one of $$$K$$$ different colors. Doludu will assign a unique integer weight from $$$1$$$ to $$$K$$$ to each color. This assignment then determines the weight of each edge: the weight of an edge is equal to the weight of its color.
Once Doludu finishes assigning weights to the colors, baluteshih will choose a spanning tree $$$\mathcal{T}$$$ of $$$G$$$. His score is the total weight of the edges in $$$\mathcal{T}$$$. As with most games, baluteshih wants to maximize his score, while Doludu wants to minimize it.
However, baluteshih finds this game incredibly boring. Not only does Doludu's color-weight assignment determine the maximum possible score he can achieve, but finding the maximum spanning tree offers no challenge for him. After playing once, he got tired of it.
Still, he recorded the game they played: which edges existed in $$$G$$$, what color each edge was, and which edges were selected in his chosen spanning tree $$$\mathcal{T}$$$. A month later, he showed this record to Doludu and said, "Hey, this is the game we played a month ago!"
But baluteshih didn't write down the exact weights Doludu assigned to each color, so Doludu became suspicious and thought baluteshih might be lying.
Your task is to help baluteshih construct a set of color weights that would make Doludu believe the record is legitimate.
Doludu will consider the record legitimate if and only if the given spanning tree $$$\mathcal{T}$$$ is a maximum spanning tree under the edge weights derived from the color weights. Doludu knows baluteshih is smart and certainly picked the best possible tree after seeing the weights, but Doludu also remembers that he chose the weights arbitrarily, so Doludu might not play optimally.
The first line contains an integer $$$T$$$, the number of test cases.
Each test case starts with a line of three integers: $$$N$$$, $$$M$$$, and $$$K$$$ — the number of vertices, edges, and colors in the graph $$$G$$$.
Then follow $$$M$$$ lines, each containing four integers $$$u_i$$$, $$$v_i$$$, $$$c_i$$$, and $$$t_i$$$, representing that the $$$i$$$-th edge connects vertices $$$u_i,v_i$$$, is painted with color $$$c_i$$$, and is part of the spanning tree $$$\mathcal{T}$$$ if $$$t_i=1$$$. If $$$t_i=0$$$, that means the $$$i$$$-th edge is not in $$$\mathcal{T}$$$.
For each test case, output a single line with $$$K$$$ integers: $$$w_1, w_2, \dots, w_K$$$, where $$$w_i$$$ is the weight assigned to color $$$i$$$.
Your solution will be considered correct if all the following conditions are satisfied:
25 7 31 2 1 12 3 2 13 4 1 14 5 2 11 5 3 02 3 1 02 4 3 06 8 52 6 1 05 1 3 11 5 3 05 6 2 15 3 1 15 1 3 04 2 2 11 4 4 1
2 3 1 2 5 4 3 1
