407537: GYM102823 F Equations

There is an array $$$A$$$ of $$$n$$$ positive integers, and $$$m$$$ equations of the form A[x] op A[y] = z, where $$$x$$$ and $$$y$$$ represent the positions in $$$A$$$, $$$op \in \{+,-,*\}$$$ and $$$z$$$ is a given integer which may differ for each equation.

However, as all the numbers in $$$A$$$ are missing, you have to find out that array and print them out.

If there are multiple arrays that do not break any equation, you just have to print out the number of valid arrays mod $$$(10^9 + 7)$$$.

The first line of the input file contains an integer $$$T$$$ ($$$1\le T\le 25$$$), describing the number of test cases.

For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$1\le n\le 10^4$$$, $$$1\le m\le 10^6$$$) described above, followed by $$$m$$$ lines.

Each of the following $$$m$$$ lines contains one string of the form xPy=z without any space ($$$x$$$, $$$y$$$, $$$z$$$ are numbers and $$$P$$$ is a character, $$$1\le x,y\le n$$$, $$$P\in\{+,-,*\}$$$, $$$0\le z\le 10^6$$$) representing one equation A[x] P A[y] = z described above.

There are no more than 5 test cases that $$$m \geq 10^5$$$.

You may need to read the sample inputs for the detail.

You should output exactly $$$T$$$ lines.

For each test case, print Case $$$x$$$: $$$d$$$ ($$$x$$$ represents the order of test case, and $$$d$$$ represents the number of solution mod $$$(10^9+7)$$$, using $$$d=-1$$$ to represent infinite ) first.

Then if the array is unique, output $$$n$$$ numbers after $$$d$$$ describing that array separated by exactly one space.

You should notice that there is only one line for one case.

4
3 2
1+2=3
1*3=9
4 3
1+2=10
2+3=3
1+4=9
2 2
1+2=3
1-2=3
3 2
1+2=4
1*3=9

Case 1: 1 1 2 9
Case 2: 1 8 2 1 1
Case 3: 0
Case 4: 2

• Sample 1:

  Equations:

  • $$$A[1]+A[2]=3$$$
  • $$$A[1] \times A[3]=9$$$

  There is only one solution: $$$A[1]=1, A[2]=2, A[3]=9$$$.

• Sample 3:

  Equations:

  • $$$A[1]+A[2]=3$$$
  • $$$A[1]-A[2]=3$$$

  There is no solution for array $$$A$$$.

• Sample 4:

  Equations:

  • $$$A[1]+A[2]=4$$$
  • $$$A[1] \times A[3]=9$$$

  There is two solutions:($$$A[1]=1, A[2]=3, A[3]=9$$$) and ($$$A[1]=3, A[2]=1, A[3]=3$$$).