One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a twist.
To play the game, Alice draws a straight line and marks $$$n$$$ points on it, indexed from $$$1$$$ to $$$n$$$. Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs $$$m$$$ operations of the following type:
After performing all $$$m$$$ operations, she wants to know the number of connected components$$$^\dagger$$$ these points form. Please help her find this number.
$$$^\dagger$$$ Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$).
The $$$i$$$-th of the following $$$m$$$ lines contains three integers $$$a_i$$$, $$$d_i$$$, and $$$k_i$$$ ($$$1 \le a_i \le a_i + k_i\cdot d_i \le n$$$, $$$1 \le d_i \le 10$$$, $$$0 \le k_i \le n$$$).
It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.
For each test case, output the number of connected components.
310 21 2 42 2 4100 119 2 4100 31 2 57 2 617 2 31
2 96 61
In the first test case, there are $$$n = 10$$$ points. The first operation joins the points $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, and $$$9$$$. The second operation joins the points $$$2$$$, $$$4$$$, $$$6$$$, $$$8$$$, and $$$10$$$. There are thus two connected components: $$$\{1, 3, 5, 7, 9\}$$$ and $$$\{2, 4, 6, 8, 10\}$$$.
In the second test case, there are $$$n = 100$$$ points. The only operation joins the points $$$19$$$, $$$21$$$, $$$23$$$, $$$25$$$, and $$$27$$$. Now all of them form a single connected component of size $$$5$$$. The other $$$95$$$ points form single-point connected components. Thus, the answer is $$$1 + 95 = 96$$$.
In the third test case, there are $$$n = 100$$$ points. After the operations, all odd points from $$$1$$$ to $$$79$$$ will be in one connected component of size $$$40$$$. The other $$$60$$$ points form single-point connected components. Thus, the answer is $$$1 + 60 = 61$$$.
Name |
---|