{"problem":{"name":"G. Tree Queries","description":{"content":"You are given a tree consisting of _n_ vertices (numbered from 1 to _n_). Initially all vertices are white. You have to process _q_ queries of two different types: 1.  1 _x_ — change the color of ver","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF825G"},"statements":[{"statement_type":"Markdown","content":"You are given a tree consisting of _n_ vertices (numbered from 1 to _n_). Initially all vertices are white. You have to process _q_ queries of two different types:\n\n1.  1 _x_ — change the color of vertex _x_ to black. It is guaranteed that the first query will be of this type.\n2.  2 _x_ — for the vertex _x_, find the minimum index _y_ such that the vertex with index _y_ belongs to the simple path from _x_ to some black vertex (a simple path never visits any vertex more than once).\n\nFor each query of type 2 print the answer to it.\n\n**Note that the queries are given in modified way**.\n\n## Input\n\nThe first line contains two numbers _n_ and _q_ (3 ≤ _n_, _q_ ≤ 106).\n\nThen _n_ - 1 lines follow, each line containing two numbers _x__i_ and _y__i_ (1 ≤ _x__i_ < _y__i_ ≤ _n_) and representing the edge between vertices _x__i_ and _y__i_.\n\nIt is guaranteed that these edges form a tree.\n\nThen _q_ lines follow. Each line contains two integers _t__i_ and _z__i_, where _t__i_ is the type of _i_th query, and _z__i_ can be used to restore _x__i_ for this query in this way: you have to keep track of the answer to the last query of type 2 (let's call this answer _last_, and initially _last_ = 0); then _x__i_ = (_z__i_ + _last_) _mod_ _n_ + 1.\n\nIt is guaranteed that the first query is of type 1, and there is at least one query of type 2.\n\n## Output\n\nFor each query of type 2 output the answer to it.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你一棵包含 #cf_span[n] 个顶点的树（编号从 #cf_span[1] 到 #cf_span[n]）。初始时所有顶点均为白色。你需要处理 #cf_span[q] 个两种不同类型的查询：\n\n对于每个类型为 #cf_span[2] 的查询，请输出其答案。\n\n*注意：查询是以修改过的方式给出的*。\n\n第一行包含两个数 #cf_span[n] 和 #cf_span[q]（#cf_span[3 ≤ n, q ≤ 106]）。\n\n接下来 #cf_span[n - 1] 行，每行包含两个数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi < yi ≤ n]），表示顶点 #cf_span[xi] 和 #cf_span[yi] 之间的边。\n\n保证这些边构成一棵树。\n\n接下来 #cf_span[q] 行，每行包含两个整数 #cf_span[ti] 和 #cf_span[zi]，其中 #cf_span[ti] 是第 #cf_span[i] 个查询的类型，而 #cf_span[zi] 可用于恢复该查询中的 #cf_span[xi]：你需要记录上一个类型为 #cf_span[2] 的查询的答案（记作 #cf_span[last]，初始时 #cf_span[last = 0]），然后 #cf_span[xi = (zi + last) mod n + 1]。\n\n保证第一个查询是类型 #cf_span[1]，且至少存在一个类型为 #cf_span[2] 的查询。\n\n对于每个类型为 #cf_span[2] 的查询，请输出其答案。\n\n## Input\n\n第一行包含两个数 #cf_span[n] 和 #cf_span[q]（#cf_span[3 ≤ n, q ≤ 106]）。接下来 #cf_span[n - 1] 行，每行包含两个数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi < yi ≤ n]），表示顶点 #cf_span[xi] 和 #cf_span[yi] 之间的边。保证这些边构成一棵树。接下来 #cf_span[q] 行，每行包含两个整数 #cf_span[ti] 和 #cf_span[zi]，其中 #cf_span[ti] 是第 #cf_span[i] 个查询的类型，而 #cf_span[zi] 可用于恢复该查询中的 #cf_span[xi]：你需要记录上一个类型为 #cf_span[2] 的查询的答案（记作 #cf_span[last]，初始时 #cf_span[last = 0]），然后 #cf_span[xi = (zi + last) mod n + 1]。保证第一个查询是类型 #cf_span[1]，且至少存在一个类型为 #cf_span[2] 的查询。\n\n## Output\n\n对于每个类型为 #cf_span[2] 的查询，请输出其答案。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of vertices and queries, respectively.  \nLet $ T = (V, E) $ be a tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E $ of size $ n-1 $.  \nLet $ c: V \\to \\{0, 1\\} $ be a vertex coloring function, where $ c(v) = 0 $ denotes white and $ c(v) = 1 $ denotes black. Initially, $ c(v) = 0 $ for all $ v \\in V $.  \nLet $ \\text{last} \\in \\mathbb{Z} $ be a state variable initialized to 0, tracking the answer to the most recent type-2 query.  \n\n**Constraints**  \n1. $ 3 \\leq n, q \\leq 10^6 $  \n2. For each edge $ (x_i, y_i) \\in E $, $ 1 \\leq x_i < y_i \\leq n $  \n3. For each query $ i \\in \\{1, \\dots, q\\} $:  \n   - $ t_i \\in \\{1, 2\\} $  \n   - $ z_i \\in \\mathbb{Z} $, and the actual vertex index is $ x_i = ((z_i + \\text{last}) \\bmod n) + 1 $  \n4. The first query has $ t_1 = 1 $, and at least one query has $ t_i = 2 $\n\n**Objective**  \nProcess $ q $ queries:  \n- If $ t_i = 1 $: toggle the color of vertex $ x_i $:  \n  $$\n  c(x_i) \\leftarrow 1 - c(x_i)\n  $$  \n- If $ t_i = 2 $: compute and output the number of edges in $ E $ whose two endpoints have different colors (i.e., the number of bichromatic edges):  \n  $$\n  \\text{last} \\leftarrow \\sum_{(u,v) \\in E} \\mathbf{1}_{c(u) \\ne c(v)}\n  $$  \n  and output $ \\text{last} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF825G","tags":["dfs and similar","graphs","trees"],"sample_group":[["4 6\n1 2\n2 3\n3 4\n1 2\n1 2\n2 2\n1 3\n2 2\n2 2","3\n2\n1"]],"created_at":"2026-03-03 11:00:39"}}