{"problem":{"name":"Sliding Edge on Torus","description":{"content":"There is an undirected graph with $N^2$ vertices. Initially, it has no edges. For each pair of integers $(i,\\ j)$ such that $0 \\leq i,\\ j < N$, the graph has a corresponding vertex called $(i,\\ j)$. Y","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc141_e"},"statements":[{"statement_type":"Markdown","content":"There is an undirected graph with $N^2$ vertices. Initially, it has no edges. For each pair of integers $(i,\\ j)$ such that $0 \\leq i,\\ j < N$, the graph has a corresponding vertex called $(i,\\ j)$.\nYou will get $Q$ queries, which should be processed in order. The $i$\\-th query, which gives you four integers $a_i,\\ b_i,\\ c_i,\\ d_i$, is as follows.\n\n*   For each $k$ $(0 \\leq k < N)$, add an edge between two vertices $((a_i+k) \\bmod N,\\ (b_i+k) \\bmod N)$ and $((c_i+k) \\bmod N,\\ (d_i+k) \\bmod N)$. Then, print the current number of connected components in the graph.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $0 \\leq a_i,\\ b_i,\\ c_i,\\ d_i < N$\n*   $(a_i,\\ b_i) \\neq (c_i,\\ d_i)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $Q$\n$a_1$ $b_1$ $c_1$ $d_1$\n$a_2$ $b_2$ $c_2$ $d_2$\n$\\vdots$\n$a_Q$ $b_Q$ $c_Q$ $d_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc141_e","tags":[],"sample_group":[["3 3\n0 0 1 2\n2 0 0 0\n1 1 2 2","6\n4\n4\n\nThe first query adds an edge between $(0,\\ 0),\\ (1,\\ 2)$, between $(1,\\ 1),\\ (2,\\ 0)$, and between $(2,\\ 2),\\ (0,\\ 1)$, changing the number of connected components from $9$ to $6$."],["4 3\n0 0 2 2\n2 3 1 2\n1 1 3 3","14\n11\n11\n\nThe graph after queries may not be simple."],["6 5\n0 0 1 1\n1 2 3 4\n1 1 5 3\n2 0 1 5\n5 0 3 3","31\n27\n21\n21\n19"]],"created_at":"2026-03-03 11:01:14"}}