{"problem":{"name":"F. PolandBall and Gifts","description":{"content":"It's Christmas time! PolandBall and his friends will be giving themselves gifts. There are _n_ Balls overall. Each Ball has someone for whom he should bring a present according to some permutation _p_","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF755F"},"statements":[{"statement_type":"Markdown","content":"It's Christmas time! PolandBall and his friends will be giving themselves gifts. There are _n_ Balls overall. Each Ball has someone for whom he should bring a present according to some permutation _p_, _p__i_ ≠ _i_ for all _i_.\n\nUnfortunately, Balls are quite clumsy. We know earlier that exactly _k_ of them will forget to bring their gift. A Ball number _i_ will get his present if the following two constraints will hold:\n\n1.  Ball number _i_ will bring the present he should give.\n2.  Ball _x_ such that _p__x_ = _i_ will bring his present.\n\nWhat is minimum and maximum possible number of kids who will **not** get their present if exactly _k_ Balls will forget theirs?\n\n## Input\n\nThe first line of input contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 106, 0 ≤ _k_ ≤ _n_), representing the number of Balls and the number of Balls who will forget to bring their presents.\n\nThe second line contains the permutation _p_ of integers from 1 to _n_, where _p__i_ is the index of Ball who should get a gift from the _i_\\-th Ball. For all _i_, _p__i_ ≠ _i_ holds.\n\n## Output\n\nYou should output two values — minimum and maximum possible number of Balls who will **not** get their presents, in that order.\n\n[samples]\n\n## Note\n\nIn the first sample, if the third and the first balls will forget to bring their presents, they will be th only balls not getting a present. Thus the minimum answer is 2. However, if the first ans the second balls will forget to bring their presents, then only the fifth ball will get a present. So, the maximum answer is 4.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"圣诞节到了！PolandBall 和他的朋友们将互相赠送礼物。总共有 #cf_span[n] 个 Balls。每个 Ball 都需要根据某个排列 #cf_span[p] 为他人送礼物，其中对所有 #cf_span[i] 都有 #cf_span[pi ≠ i]。\n\n不幸的是，Balls 非常笨拙。我们事先知道，恰好有 #cf_span[k] 个 Ball 会忘记带礼物。Ball #cf_span[i] 能收到礼物，当且仅当满足以下两个条件：\n\n如果恰好有 #cf_span[k] 个 Ball 忘记带礼物，那么最少和最多可能有多少个孩子收不到礼物？\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 106]，#cf_span[0 ≤ k ≤ n]），分别表示 Balls 的数量和忘记带礼物的 Balls 数量。\n\n第二行包含一个从 #cf_span[1] 到 #cf_span[n] 的排列 #cf_span[p]，其中 #cf_span[pi] 表示第 #cf_span[i] 个 Ball 应该把礼物送给哪个 Ball 的编号。对所有 #cf_span[i]，都有 #cf_span[pi ≠ i]。\n\n你应该输出两个值 —— 收不到礼物的 Balls 的最小和最大可能数量，按此顺序输出。\n\n在第一个样例中，如果第三和第一个 Ball 忘记带礼物，那么只有他们两个收不到礼物。因此最小答案是 #cf_span[2]。然而，如果第一和第二个 Ball 忘记带礼物，那么只有第五个 Ball 能收到礼物。因此最大答案是 #cf_span[4]。\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 106]，#cf_span[0 ≤ k ≤ n]），分别表示 Balls 的数量和忘记带礼物的 Balls 数量。第二行包含一个从 #cf_span[1] 到 #cf_span[n] 的排列 #cf_span[p]，其中 #cf_span[pi] 表示第 #cf_span[i] 个 Ball 应该把礼物送给哪个 Ball 的编号。对所有 #cf_span[i]，都有 #cf_span[pi ≠ i]。\n\n## Output\n\n你应该输出两个值 —— 收不到礼物的 Balls 的最小和最大可能数量，按此顺序输出。\n\n[samples]\n\n## Note\n\n在第一个样例中，如果第三和第一个 Ball 忘记带礼物，那么只有他们两个收不到礼物。因此最小答案是 #cf_span[2]。然而，如果第一和第二个 Ball 忘记带礼物，那么只有第五个 Ball 能收到礼物。因此最大答案是 #cf_span[4]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^6 $, $ 0 \\leq k \\leq n $.  \nLet $ p \\in S_n $ be a permutation of $ \\{1, 2, \\dots, n\\} $ such that $ p(i) \\neq i $ for all $ i $.  \nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, 2, \\dots, n\\} $ and $ E = \\{(i, p(i)) \\mid i \\in V\\} $.  \nSince $ p $ is a permutation with no fixed points, $ G $ is a disjoint union of directed cycles of length at least 2.\n\nLet $ C_1, C_2, \\dots, C_m $ be the cycles in $ G $, with lengths $ \\ell_1, \\ell_2, \\dots, \\ell_m \\geq 2 $, and $ \\sum_{j=1}^m \\ell_j = n $.\n\nLet $ F \\subseteq V $ be the set of $ k $ Balls who forget to bring gifts, $ |F| = k $.\n\nA Ball $ i $ **does not receive** a gift if and only if the Ball who is supposed to give to $ i $ (i.e., the unique $ j $ such that $ p(j) = i $) is in $ F $.\n\nLet $ R(F) = \\{ i \\in V \\mid p^{-1}(i) \\in F \\} $ be the set of Balls who do not receive a gift.\n\n**Constraints**  \n1. $ |F| = k $  \n2. $ p(i) \\neq i $ for all $ i $  \n3. $ G $ consists of disjoint cycles of length $ \\geq 2 $\n\n**Objective**  \nCompute:  \n- $ \\min_{F \\subseteq V, |F|=k} |R(F)| $  \n- $ \\max_{F \\subseteq V, |F|=k} |R(F)| $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF755F","tags":["bitmasks","dp","greedy"],"sample_group":[["5 2\n3 4 1 5 2","2 4"],["10 1\n2 3 4 5 6 7 8 9 10 1","2 2"]],"created_at":"2026-03-03 11:00:39"}}