{"raw_statement":[{"iden":"statement","content":"Pedro and Lucas are two brothers who look extremely alike in many ways, despite not being twins. One day, their friends Gabriel Mendes and Gabriel Pessoa decided to know, once and for all, if they really looked that similar, and, for that, they asked for the brothers to go for a walk on the park. They will walk the same total distance, but doing random moves. Therefore, in order to actually know the path traveled by them, Pedro and Lucas need to write their positions on every change of direction they make, or simply mark their current position whenever they wanted, until they decided to stop.\n\nMendes and Pessoa now decided to analyze the trajectory that was created by the movements of each of the brothers, and the result was really impressive!\n\nLet us call each of the $N$ points marked by Pedro as $P_i$, and the $M$ points marked by Lucas as $L_i$. They verified that for each two consecutive points on each of the brothers' path (i.e. the segments $[ P_i, P_{i + 1} ]$ and $[ L_i, L_{i + 1} ]$), the distance between them were equal. That is, \n\n  \n\nThat also implied that the brothers actually marked the same number ($K$) of points. How crazy is that?\n\nMendes and Pessoa were so impressed that they thought:\n\nYour goal is to print the minimum number of points that would need to be marked on the path of each one of the Gabriels (Mendes and Pessoa), so that every distance between consecutive points on their paths would be exactly the same.\n\nThe first line of input consists of two integers $N$ and $M$, $[ 2 <= N, M <= 20 thin 000 ]$, that represent, respectively:\n\n$med displaystyle bullet med$ The number of points marked by Mendes;\n\n$med displaystyle bullet med$ The number of points marked by Pessoa;\n\nThe following $N$ lines contain the points $P_i$ marked by Mendes $[ -10^9 <= x_{P_(i}), y_{P_(i}) <= 10^9 ]$;\n\nA blank line separates the lists of points of Mendes and Pessoa;\n\nThen, the next $M$ lines contain the points $Q_i$ marked by Pessoa $[ -10^9 <= x_{Q_(i}), y_{Q_(i}) <= 10^9 ]$;\n\nThe output consists of one integer: The minimum number of points that need to be added on Mendes' path and Pessoas' path.\n\n- The points coordinates may not be integers;\n\n- Two distances can be considered equal if $a b s (D_a -D_b) <= 10^(-5)$;\n\n- The length of each segment must be equal in both paths.\n\n"},{"iden":"input","content":"The first line of input consists of two integers $N$ and $M$, $[ 2 <= N, M <= 20 thin 000 ]$, that represent, respectively:$med displaystyle bullet med$ The number of points marked by Mendes;$med displaystyle bullet med$ The number of points marked by Pessoa;The following $N$ lines contain the points $P_i$ marked by Mendes $[ -10^9 <= x_{P_(i}), y_{P_(i}) <= 10^9 ]$;A blank line separates the lists of points of Mendes and Pessoa;Then, the next $M$ lines contain the points $Q_i$ marked by Pessoa $[ -10^9 <= x_{Q_(i}), y_{Q_(i}) <= 10^9 ]$;"},{"iden":"output","content":"The output consists of one integer: The minimum number of points that need to be added on Mendes' path and Pessoas' path."},{"iden":"note","content":"- The points coordinates may not be integers;- Two distances can be considered equal if $a b s (D_a -D_b) <= 10^(-5)$;- The length of each segment must be equal in both paths."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ \\mathcal{F}_n $ be the set of all labelled forests on $ n $ vertices with vertex labels $ \\{1, 2, \\dots, n\\} $.  \nLet $ \\delta(i, j) $ denote the shortest path distance between vertices $ i $ and $ j $ in a forest $ G \\in \\mathcal{F}_n $, or $ m $ if no path exists.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\times 10^5 $  \n2. $ n \\leq m \\leq 998244352 $  \n3. $ T \\leq 2 \\times 10^5 $ test cases  \n4. All computations are modulo $ 998244353 $\n\n**Objective**  \nFor each test case, compute the expected value of  \n$$\n\\sum_{i=1}^{n} \\sum_{j=i+1}^{n} \\delta^2(i, j)\n$$  \nover all forests $ G \\in \\mathcal{F}_n $ chosen uniformly at random, and output the result modulo $ 998244353 $ as the integer $ r $ satisfying  \n$$\nr \\equiv \\mathbb{E}\\left[\\sum_{i=1}^{n} \\sum_{j=i+1}^{n} \\delta^2(i, j)\\right] \\pmod{998244353}\n$$","simple_statement":"Given a random labeled forest with n vertices, compute the expected value of the sum of squared distances between all pairs of vertices, where missing paths count as distance m. Output the result modulo 998244353.","has_page_source":false}