{"problem":{"name":"B. Derangement","description":{"content":"A permutation of n numbers is a sequence of integers from 1 to n where each number is occurred exactly once. If a permutation p1, p2, ..., pn has an index i such that pi = i, this index is called a fi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10097B"},"statements":[{"statement_type":"Markdown","content":"A permutation of n numbers is a sequence of integers from 1 to n where each number is occurred exactly once. If a permutation p1, p2, ..., pn has an index i such that pi = i, this index is called a fixed point.\n\nA derangement is a permutation without any fixed points.\n\nLet's denote the operation swap(a, b) as swapping elements on positions a and b.\n\nFor the given permutation find the minimal number of swap operations needed to turn it into derangement.\n\nThe first line contains an integer n (2 ≤ n ≤ 200000) — the number of elements in a permutation.\n\nThe second line contains the elements of the permutation — n distinct integers from 1 to n.\n\nIn the first line output a single integer k — the minimal number of swap operations needed to transform the permutation into derangement.\n\nIn each of the next k lines output two integers ai and bi (1 ≤ ai, bi ≤ n) — the arguments of swap operations.\n\nIf there are multiple possible solutions, output any of them.\n\n## Input\n\nThe first line contains an integer n (2 ≤ n ≤ 200000) — the number of elements in a permutation.The second line contains the elements of the permutation — n distinct integers from 1 to n.\n\n## Output\n\nIn the first line output a single integer k — the minimal number of swap operations needed to transform the permutation into derangement.In each of the next k lines output two integers ai and bi (1 ≤ ai, bi ≤ n) — the arguments of swap operations.If there are multiple possible solutions, output any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 200000 $.  \nLet $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nA *fixed point* is an index $ i $ such that $ \\pi_i = i $.  \nA *derangement* is a permutation with no fixed points.\n\n**Constraints**  \n- $ \\pi $ is a bijection from $ \\{1, \\dots, n\\} $ to $ \\{1, \\dots, n\\} $.  \n- The goal is to transform $ \\pi $ into a derangement using the minimum number of transpositions (swaps).\n\n**Objective**  \nFind the minimum number $ k $ of swap operations $ \\text{swap}(a_i, b_i) $ such that the resulting permutation $ \\pi' $ satisfies $ \\pi'_i \\neq i $ for all $ i \\in \\{1, \\dots, n\\} $, and output the sequence of swaps achieving this minimum.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10097B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}