CF2041G Grid Game

Claire loves drawing lines. She receives a sheet of paper with an $ n \times n $ grid and begins drawing "lines" on it. Well—the concept of a "line" here is not what we usually think of. Claire refers each line to be a set of consecutive vertical grid cells. When she draws a line, these cells are all covered with black ink. Initially, all the cells are white, and drawing lines turns some of them black. After drawing a few lines, Claire wonders: how many ways she can color an additional white cell black so that the remaining white cells do not form a single connected component. Two cells are directly connected if they share an edge. Two cells $ x $ and $ y $ are indirectly connected if there exists a sequence of cells $ c_0, c_1, \ldots, c_k $ with $ k > 1 $ such that $ c_0 = x $ , $ c_k = y $ , and for every $ i \in \{1, 2, \ldots, k\} $ the cells $ c_i $ and $ c_{i-1} $ are directly connected. A set of cells forms a single connected component if each pair of cells in the set is either directly or indirectly connected. The grid has $ n $ rows and $ n $ columns, both indexed from $ 1 $ to $ n $ . Claire will draw $ q $ lines. The $ i $ -th line is drawn in the $ y_i $ -th column, from the $ s_i $ -th row to the $ f_i $ -th row, where $ s_i \leq f_i $ for each $ i \in \{1, 2, \ldots, q\} $ . Note that the cells that are passed by at least one of the $ q $ lines are colored black. The following figure shows an example of a $ 20\times 20 $ grid with $ q=67 $ lines. The grid cells marked with red star symbols refer to the cells such that, if Claire colors that cell black, all white cells no longer form a single connected component. You may assume that, after drawing the $ q $ lines, the remaining white cells form a single connected component with at least three white cells.

The first line contains exactly one integer $ t $ , indicating the number of test cases. For each test case, it begins with a line containing exactly two integers $ n $ and $ q $ . This indicates that the grid is $ n $ by $ n $ and that Claire draws $ q $ lines on it. Then $ q $ lines follow. For each $ i \in \{1, 2, \ldots, q\} $ , the $ i $ -th line among the $ q $ lines contains exactly three integers $ y_i $ , $ s_i $ , and $ f_i $ . - $ 1\le t \le 125 $ - $ 2\leq n \leq 10^9 $ - $ q\ge 1 $ ; the sum of all $ q $ values is at most $ 10^5 $ . - $ 1\leq y_i \leq n $ - $ 1\leq s_i \leq f_i \leq n $ - There are at least three white cells and all white cells form a connected component.

Print an integer on a line, indicating how many ways Claire can color an additional white cell black so that the remaining white cells do not form a single connected component.