{"raw_statement":[{"iden":"statement","content":"In 2020, due to $i s s u e s$ worldwide, $C u p i d o n u s$ moved his tutoring program online. For a small reasonable amount (4000 - 5000 Euros) he can teach you the ways of the $c u p i d$, so you will be able to become a $C u p i d o n$. Of course inferior to $C u p i d o n u s$.\n\nAs a result $N$ smarties registered for his program. Since $C u p i d o n u s$ is really busy, he decided to organize a test in order to select the right candidate in one go. As a result, he aligned all the smarties on the $O Y$ axis and asked each of them to shoot an arrow in the semiplane with $x > 0$. $C u p i d o n u s$ will select the maximum number of smarties such that any two trajectories of their arrows do $N O T$ intersect.\n\n$C u p i d o n u s$ asked you to supervise the test and tell him how many candidates will be selected.\n\nThe first line of the input will contain the number of test cases $T$ ($1 <= T <= 100000$).\n\nThe first line of each test case will be the number $N$ ($1 <= N <= 10^5$), the number of smarties who registered to become a $C u p i d o n$.\n\nThe following $N$ lines of each test case will each contain $3$ integers $a_i$, $x_i$, $y_i$ ($-2^(52) <= a_i, y_i <= 2^(52)$, $1 <= x_i <= 2^(52)$, $1 <= i <= N$), the position of the $i$th smartie on the $O Y$ axis and the coordinates where his arrow landed. All $a_i$ are pairwise distinct.\n\nIt is guaranteed that the sum of $N$ over all test cases does not exceed $500000$.\n\nThe output should contain $T$ lines, each containing the answer to the corresponding test case.\n\nFor the first example we can choose the smarties with indexes: 2, 3, 5. See image below.\n\n"},{"iden":"input","content":"The first line of the input will contain the number of test cases $T$ ($1 <= T <= 100000$).The first line of each test case will be the number $N$ ($1 <= N <= 10^5$), the number of smarties who registered to become a $C u p i d o n$.The following $N$ lines of each test case will each contain $3$ integers $a_i$, $x_i$, $y_i$ ($-2^(52) <= a_i, y_i <= 2^(52)$, $1 <= x_i <= 2^(52)$, $1 <= i <= N$), the position of the $i$th smartie on the $O Y$ axis and the coordinates where his arrow landed. All $a_i$ are pairwise distinct.It is guaranteed that the sum of $N$ over all test cases does not exceed $500000$."},{"iden":"output","content":"The output should contain $T$ lines, each containing the answer to the corresponding test case."},{"iden":"note","content":"For the first example we can choose the smarties with indexes: 2, 3, 5. See image below.  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected, unweighted, connected graph with $ |V| = n $, $ |E| = m $, and no self-loops or parallel edges.  \nEach edge $ e_i = (u_i, v_i) \\in E $ is labeled with a character $ c_i \\in \\Sigma $, where $ \\Sigma $ is the set of lowercase Latin letters.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 200000 $  \n2. $ 1 \\leq m \\leq 200000 $  \n3. For all $ e_i = (u_i, v_i, c_i) $, $ 1 \\leq u_i, v_i \\leq n $, $ u_i \\ne v_i $, $ c_i \\in \\text{a-z} $  \n\n**Objective**  \nFind a path $ P = (v_0, v_1, \\dots, v_k) $ from $ v_0 = 1 $ to $ v_k = n $ such that:  \n- $ k $ is minimized (shortest path),  \n- Among all shortest paths, the string $ s = c_1 c_2 \\dots c_k $, where $ c_j $ is the label on edge $ (v_{j-1}, v_j) $, is lexicographically minimal.  \n\nOutput:  \n- The length $ k $ of the path,  \n- The sequence of vertices $ v_0, v_1, \\dots, v_k $,  \n- The string $ s $ of edge labels along the path.","simple_statement":"Find the shortest path from vertex 1 to vertex n in an undirected graph where each edge has a letter. If multiple shortest paths exist, choose the one with the lexicographically smallest string of letters. Output the path length, the vertex sequence, and the letter string.","has_page_source":false}