408526: GYM103181 G Complicated Schedule

Petrick has a very complicated schedule. He is a busy businessman and has a lot of tasks to do during the day, one of them being to propose some easy to implement problems that contestants enjoy working on. Coming back to Petrick, he needs to take care that some of its tasks must start way before others and he does not care when he finishes them. Also, he can solve more tasks at the same time! Petrick got $$$N$$$ jobs during the day (numbered from $$$0$$$ to $$$N -- 1$$$) and $$$M$$$ restrictions of two types. The first type of restriction says that the job number $$$X$$$ must start no later than $$$L$$$ seconds before the job number $$$Y$$$ starts. In this case, the job number $$$Y$$$ must start at least $$$L$$$ seconds after the beginning of the day. The second type of restriction says that the job number $$$X$$$ must start no later than $$$L$$$ seconds after the job number $$$Y$$$ starts. Petrick has only one day to solve his tasks and his day starts at second $$$0$$$ and ends at second $$$10^{12}$$$. Help him find out if there is a way to solve each task in the interval of seconds $$$[0, 10^{12}]$$$.

The first line of the input contains a number $$$1 \leq T \leq 13$$$, the number of tests. The first line of each test contains 2 integers $$$2 \leq N \leq 1000$$$, the number of tasks, and $$$1 \leq M \leq 1000$$$, the number of restrictions. The following $$$M$$$ lines each contain integers ($$$R, X, Y, L$$$) signifying that we have a restriction of type $$$R$$$ ($$$1 \leq R \leq 2$$$) between job number $$$X$$$ and job $$$Y$$$ as described above ($$$0 \leq X, Y \leq N - 1,$$$ $$$0 \leq L \leq 10^{9}$$$).

The output should contain $$$T$$$ lines, each containing an answer to a test, the starting times (in seconds) of each task separated by spaces or $$$-1$$$ in a case with no solution. If there are more solutions over the interval of time $$$[0, 10^{12}]$$$ you can output any of them.

2
3 2
2 0 1 0
1 1 2 1
2 2
1 0 1 10
1 1 0 10

0 0 1 
-1