{"problem":{"name":"[COTS 2024] 划分 Particija","description":{"content":" 给定正整数 $ N $。 集合 $ \\{1, 2, \\ldots, N\\} $ 的**划分**为由非空集合组成的集族，满足： - $\\forall 1\\le i\\le N$，$i$ 出现在**恰好一个**集合中。 例如，$\\{\\{1,3\\},\\{2,4\\},\\{5\\}\\}$ 是集合 $ \\{1, 2, 3, 4, 5\\} $ 的一个划分。 可以用数列 $ [x_1, x_2, \\ldot","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10683"},"statements":[{"statement_type":"Markdown","content":"给定正整数 $ N $。\n\n集合 $ \\{1, 2, \\ldots, N\\} $ 的**划分**为由非空集合组成的集族，满足：\n- $\\forall 1\\le i\\le N$，$i$ 出现在**恰好一个**集合中。\n\n例如，$\\{\\{1,3\\},\\{2,4\\},\\{5\\}\\}$ 是集合 $ \\{1, 2, 3, 4, 5\\} $ 的一个划分。\n\n可以用数列 $ [x_1, x_2, \\ldots, x_N ]$ 来表示划分。当且仅当 $ x_i = x_j $ 时，$ i $ 和 $ j $ 在同一个集合中。上面提到的划分 $\\{\\{1,3\\},\\{2,4\\},\\{5\\}\\}$ 可以由数列 $[1, 2, 1, 2, 3]$ 或者 $[5, 1, 5, 1, 4]$ 表示。\n\nPatricija 拥有两个划分：第一个划分用数列 $ [a_1, a_2, \\ldots, a_N] $ 表示，第二个划分用数列 $ [b_1, b_2, \\ldots, b_N] $ 表示。\n\nPatricija 想知道以下问题的答案：如果她使用这两个划分中的集合，来构造集合 $ \\{1, 2, \\ldots, N\\} $ 的划分，至少需要多少个集合。\n\n给定参数 $k\\in \\{0,1,2\\}$，\n\n- 当 $k=0$ 时，你需要回答原问题的答案。\n- 当 $k=1$ 时，允许更改 $2N$ 个数字（$a_1,\\cdots,a_N,b_1,\\cdots,b_N$）中**至多**一个，**最小化**构造划分需要的最少集合数。\n- 当 $k=2$ 时，允许更改 $2N$ 个数字（$a_1,\\cdots,a_N,b_1,\\cdots,b_N$）中**至多**一个，**最大化**构造划分需要的最少集合数。\n\n请注意，你需要保证在你修改后，$\\forall 1\\le i\\le N$，$1\\le a_i,b_i\\le N$。\n\n## Input\n\n**本题单个测试点内有多组测试数据。**\n\n第一行，两个整数 $T,k$，分别表示测试数据数量，以及参数。\n\n接下来依次描述 $T$ 组测试数据：\n\n对于每组测试数据，输入三行。\n\n第一行，一个正整数 $N$，含义见题面；\n\n第二行，$N$ 个正整数，依次表示 $a_1,a_2,\\cdots,a_N$；\n\n第三行，$N$ 个正整数，依次表示 $b_1,b_2,\\cdots,b_N$。\n\n## Output\n\n对于每组测试数据，输出一行一个整数，表示所求的答案。\n\n[samples]\n\n## Background\n\n译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T1。$\\texttt{1s,512M}$。\n\n## Note\n\n#### 样例解释\n\n样例 $1$ 解释：\n\n对于第一组数据，第一个划分为 $\\{\\{1,2\\},\\{3\\},\\{4\\}\\}$，第二个划分为 $\\{\\{1\\},\\{2\\},\\{3,4\\}\\}$。选取 $\\{1,2\\},\\{3,4\\}$ 即可。\n\n对于第二组数据，第一个划分为 $\\{\\{1,2,3,4\\},\\{5\\},\\{6\\},\\{7\\}\\}$，第二个划分为 $\\{\\{1\\},\\{2\\},\\{3\\},\\{4,5,6,7\\}\\}$。选取第一个划分或第二个划分即可。\n\n#### 数据范围\n\n对于 $100\\%$ 的数据，保证：\n\n- $1\\le T\\le 200\\, 000$，$k\\in \\{0,1,2\\}$；\n- $1\\le a_i,b_i\\le N$；\n- $1\\le N,\\sum N\\le 200\\, 000$。\n\n| 子任务编号 | 分值 | 约束  |\n|:-----:|:------:|:-------:|\n| $1$  | $7$  | $k=0,N\\le 8,\\sum 2^N\\le 10^5$   |\n| $2$  | $23$  | $k=0$  |\n| $3$  | $15$  | $k=1,N\\le 1\\, 000,\\sum N^2\\le 10^6$ |\n| $4$  | $16$  | $k=1$ |\n| $5$  | $19$  | $k=2,N\\le 1\\, 000,\\sum N^2\\le 10^6$ |\n| $6$  | $20$  | $k=2$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10683","tags":["2024","O2优化","二分图","COTS（克罗地亚）"],"sample_group":[["2 0\n4 \n1 1 2 3\n1 2 3 3\n7\n1 1 1 1 2 3 4\n1 2 3 4 4 4 4","2\n4"],["3 1\n4\n1 1 2 3\n1 2 3 3\n4\n1 1 1 1\n1 2 3 3\n7\n1 1 1 1 2 3 4\n1 2 3 4 4 4 4","2\n1\n2"],["3 2\n4 \n1 1 2 3\n1 2 3 3\n4\n1 1 1 3\n1 2 3 3\n7\n1 1 1 2 3 4 5\n1 2 3 4 4 4 4","3\n3\n4"]],"created_at":"2026-03-03 11:09:25"}}