M. Minimax Spanning Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

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}$$$.

  • $$$1 \leq T \leq 2.5 \cdot 10^5$$$
  • $$$2 \leq N \leq 5 \cdot 10^5$$$
  • $$$N - 1 \leq M \leq 5 \cdot 10^5$$$
  • $$$1 \leq K \leq M$$$
  • $$$1 \leq u_i, v_i \leq N$$$
  • $$$1 \leq c_i \leq K$$$
  • $$$t_i \in \{0,1\}$$$
  • $$$G$$$ is guaranteed to be connected.
  • The graph $$$G$$$ may contain multiple edges, but no self-loops.
  • The edges with $$$t_i = 1$$$ form a spanning tree of $$$G$$$.
  • It is guaranteed that a valid solution exists.
  • It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
  • It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
Output

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:

  • $$$1 \leq w_i \leq K$$$
  • $$$w_i \neq w_j$$$ for all $$$i \neq j$$$
  • Given that the $$$i$$$-th edge's weight is $$$w_{c_i}$$$, the tree $$$\mathcal{T}$$$ is a maximum spanning tree of $$$G$$$. Note that the maximum spanning tree may not be unique. Your answer is considered correct as long as $$$\mathcal{T}$$$ has the maximum total weight.
Example
Input
2
5 7 3
1 2 1 1
2 3 2 1
3 4 1 1
4 5 2 1
1 5 3 0
2 3 1 0
2 4 3 0
6 8 5
2 6 1 0
5 1 3 1
1 5 3 0
5 6 2 1
5 3 1 1
5 1 3 0
4 2 2 1
1 4 4 1
Output
2 3 1
2 5 4 3 1