{"problem":{"name":"I. Сколько весит карма?","description":{"content":"Ур и Ар были странствующими магами, неразлучными друзьями с самого раннего детства. Они приходили в какой-нибудь городок, показывали там всякие фокусы, танцы с бубнами, проводили сеансы телепатии - в ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10120I"},"statements":[{"statement_type":"Markdown","content":"Ур и Ар были странствующими магами, неразлучными друзьями с самого раннего детства. Они приходили в какой-нибудь городок, показывали там всякие фокусы, танцы с бубнами, проводили сеансы телепатии - в общем, по всякому развлекали народ, а взамен получали кров и пищу.\n\nНо в одном городке все пошло не по плану. Оказалось, что горожане поклонялись могучей богине справедливости и правосудия Анасте, и считали любую магию несправедливостью по отношению к суровой реальности. Ур и Ар были схвачены, приведены в храм Анасты и оставлены дожидаться пришествия богини.\n\nИ ведь дождались! Ровно в полночь Анаста явилась к напуганным до смерти магам. Она была слепа (как и всякое правосудие), а в руке держала невероятно большие рычажные весы. Когда человек вставал на одну чашу весов, на другой появлялись совершенные им несправедливости.\n\nУр и Ар не были злодеями, убивавшими детей и грабившими беззащитных стариков, но и в их жизни были мелкие косяки со справедливостью. Косяки никогда не повторялись, ведь друзья всегда хотели попробовать что-нибудь новое. Некоторые вещи они совершали вместе, а что-то Ур (или Ар) делал за двоих, беря на себя двойную ответственность.\n\nПоэтому, когда Ур и Ар встали на разные чаши весов, на чашах появилось ровно 2N несправедливостей (по N на каждой чаше), занумерованных от 1 до n (каждая несправедливость встречается ровно 2 раза).\n\nАнаста заявила, что когда весы придут в равновесие, она решит их судьбу. Ур и Ар подумали, что пока весы колеблются, они могут незаметно сделать набор несправедливостей и даже порядок расположения несправедливостей в наборах на чашах полностью одинаковым. Тогда Анасте придется выбрать им полностью одинаковую судьбу, и друзья смогут и дальше продолжить свои приключения вместе.\n\nВесы оказались довольно неустойчивы, поэтому за одно действие Ур может перекинуть только одну несправедливость Ару, а Ар одновременно перекинуть несправедливость со своей чаши Уру. \n\nНа кону судьба их дружбы, поэтому Ур и Ар просят помочь вас и подсказать им возможный порядок перекидывания несправедливостей между чашами. Помните, что весы Анасты скоро придут в равновесие, поэтому маги успеют сделать не более 4n перекидываний.\n\nВ первой строке вводится число n (1 ≤ n ≤ 105) - количество несправедливостей на каждой из чаш весов.\n\nВ следующей строке вводятся n чисел ai (1 ≤ ai ≤ n) - порядок номеров несправедливостей на чаше весов с Уром.\n\nВ последней строке вводятся n чисел bi (1 ≤ bi ≤ n) - порядок номеров несправедливостей на чаше весов с Аром.\n\nГарантируется, что среди чисел ai и bi есть ровно два числа 1, два числа 2, ..., два числа n.\n\nВ первой строке выведите k (0 ≤ k ≤ 4n)- количество действий магов, которое приведет к совпадению итоговых наборов несправедливостей и порядка расположения несправедливостей в наборах.\n\nВ каждой из следуюших k строк выведите по два числа fi и si - позиции несправедливостей на чаше Ура и Ара соответственно, которые необходимо поменять местами в i-ом действии.\n\nРассмотрим пример:\n\nПеред первым действием a = [1, 1, 2], b = [2, 3, 3].\n\n1) f1 = 2, s1 = 3 - меняются местами a2 и b3 - a = [1, 3, 2], b = [2, 3, 1];\n\n2) f2 = 3, s2 = 3 - меняются местами a3 и b3 - a = [1, 3, 1], b = [2, 3, 2];\n\n3) f3 = 3, s3 = 1 - меняются местами a3 и b1 - a = [1, 3, 2], b = [1, 3, 2];\n\n4) f4 = 3, s4 = 3 - меняются местами a3 и b3 - a = [1, 3, 2], b = [1, 3, 2].\n\nОбратите внимание, что маги имели право остановиться уже после 3-го действия, так как наборы уже полностью совпадали.\n\n## Входные Данные\n\nВ первой строке вводится число n (1 ≤ n ≤ 105) - количество несправедливостей на каждой из чаш весов.В следующей строке вводятся n чисел ai (1 ≤ ai ≤ n) - порядок номеров несправедливостей на чаше весов с Уром.В последней строке вводятся n чисел bi (1 ≤ bi ≤ n) - порядок номеров несправедливостей на чаше весов с Аром.Гарантируется, что среди чисел ai и bi есть ровно два числа 1, два числа 2, ..., два числа n.\n\n## Выходные Данные\n\nВ первой строке выведите k (0 ≤ k ≤ 4n)- количество действий магов, которое приведет к совпадению итоговых наборов несправедливостей и порядка расположения несправедливостей в наборах.В каждой из следуюших k строк выведите по два числа fi и si - позиции несправедливостей на чаше Ура и Ара соответственно, которые необходимо поменять местами в i-ом действии.\n\n## Пример\n\nВходные данные31 1 22 3 3Выходные данные42 33 33 13 3\n\n## Примечание\n\nРассмотрим пример:Перед первым действием a = [1, 1, 2], b = [2, 3, 3].1) f1 = 2, s1 = 3 - меняются местами a2 и b3 - a = [1, 3, 2], b = [2, 3, 1];2) f2 = 3, s2 = 3 - меняются местами a3 и b3 - a = [1, 3, 1], b = [2, 3, 2];3) f3 = 3, s3 = 1 - меняются местами a3 и b1 - a = [1, 3, 2], b = [1, 3, 2];4) f4 = 3, s4 = 3 - меняются местами a3 и b3 - a = [1, 3, 2], b = [1, 3, 2].Обратите внимание, что маги имели право остановиться уже после 3-го действия, так как наборы уже полностью совпадали.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of distinct injustices, with two copies of each injustice numbered $ 1 $ to $ n $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of injustices on Ur’s side.  \nLet $ B = (b_1, b_2, \\dots, b_n) $ be the sequence of injustices on Ar’s side.  \nEach integer $ i \\in \\{1, \\dots, n\\} $ appears exactly twice across $ A \\cup B $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a_i, b_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Each value from $ 1 $ to $ n $ appears exactly twice in $ A \\cup B $.  \n4. At most $ 4n $ swaps are allowed.\n\n**Objective**  \nFind a sequence of swaps $ (f_j, s_j) $ for $ j = 1, \\dots, k $ (where $ 0 \\leq k \\leq 4n $) such that after swapping $ a_{f_j} $ with $ b_{s_j} $ in each step, the final sequences $ A $ and $ B $ are identical.  \nEach swap exchanges one element from $ A $ with one element from $ B $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10120I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}