Score : 1200 points
We have N boxes numbered 1 to N, and M balls numbered 1 to M. Currently, Ball i is in Box A_i.
You can do the following operation:
Since the balls are very easy to break, you cannot move Ball i more than C_i times in total. Within this limit, you can do the operation any number of times.
Your objective is to have Ball i in Box B_i for every i (1 \leq i \leq M). Determine whether this objective is achievable. If it is, also find the minimum number of operations required to achieve it.
Input is given from Standard Input in the following format:
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
If the objective is unachievable, print -1; if it is achievable, print the minimum number of operations required to achieve it.
3 3 1 2 1 2 1 1 1 3 2
3
We can achieve the objective in three operations, as follows:
2 2 1 2 1 2 1 1
-1
5 5 1 2 1 2 1 1 1 3 2 4 5 1 5 4 1
6
1 1 1 1 1
0