N. Paths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed acyclic graph, with each edge $$$i$$$ having a weight in the range $$$[l_i, r_i]$$$. Assign weights to each edge such that all paths from $$$1$$$ to $$$n$$$ have the same cost. It is guaranteed that node $$$1$$$ is the only source$$$^{\text{∗}}$$$ and node $$$n$$$ is the only sink$$$^{\text{†}}$$$.

$$$^{\text{∗}}$$$A source node has no incoming edges, and has outgoing edges.

$$$^{\text{†}}$$$A sink node has no outgoing edges, and has incoming edges.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{2}$$$). The description of the test cases follows.

The first line of each test case contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^{3}$$$, $$$n - 1 \leq m \leq \min(4 \cdot 10^{3}, \frac{n(n-1)}{2})$$$) — the number of nodes and edges in the graph.

The next $$$m$$$ lines contain two integers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$, and $$$r_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq l_i \leq r_i \leq 10^{9}$$$) — the edge endpoints, and the range bounding the edge weight. It is guaranteed that there are no multiedges.

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

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-4$$$ satisfies $$$l_i = 1$$$ and $$$r_i = 10^9$$$.

Tests $$$5-20$$$ satisfy no additional constraints.

Output

If no valid construction exists, print $$$-1$$$. Otherwise, print the edge weights, in order of input.

Example
Input
2
4 4
1 2 1 10
1 3 1 10
2 4 1 10
3 4 1 10
4 4
1 2 5 5
1 3 10 10
2 4 1 1
3 4 1 1
Output
10 10 10 10
-1
Note

For the first test case, assigning all the edge weights to $$$10$$$ ensures that all paths from $$$1$$$ to $$$n$$$ have the same cost.

For the second test case, we can show that any weight assignment results in paths from $$$1$$$ to $$$n$$$ with differing weights.

—

Problem Idea: dutin

Problem Preparation: eysbutno

Occurrences: Advanced J