{"problem":{"name":"E. Petr and Permutations","description":{"content":"Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF987E"},"statements":[{"statement_type":"Markdown","content":"Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of numbers from $1$ to $n$ and then $3n$ times takes a random pair of different elements and swaps them. Alex envies Petr and tries to imitate him in all kind of things. Alex has also come up with a problem about random permutation. He generates a random permutation just like Petr but swaps elements $7n+1$ times instead of $3n$ times. Because it is more random, OK?!\n\nYou somehow get a test from one of these problems and now you want to know from which one.\n\n## Input\n\nIn the first line of input there is one integer $n$ ($10^{3} \\le n \\le 10^{6}$).\n\nIn the second line there are $n$ distinct integers between $1$ and $n$ — the permutation of size $n$ from the test.\n\nIt is guaranteed that all tests except for sample are generated this way: First we choose $n$ — the size of the permutation. Then we randomly choose a method to generate a permutation — the one of Petr or the one of Alex. Then we generate a permutation using chosen method.\n\n## Output\n\nIf the test is generated via Petr's method print \"_Petr_\" (without quotes). If the test is generated via Alex's method print \"_Um_nik_\" (without quotes).\n\n[samples]\n\n## Note\n\nPlease note that the sample is not a valid test (because of limitations for $n$) and is given only to illustrate input/output format. Your program **still has to print correct answer to this test** to get AC.\n\nDue to randomness of input hacks in this problem are forbidden.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Petr 喜欢设计关于随机生成数据的问题。这次的问题是关于随机排列的。他决定通过以下方式生成一个随机排列：从数字 $1$ 到 $n$ 的恒等排列开始，然后进行 $3 n$ 次操作，每次随机选取两个不同的元素并交换它们。Alex 羡慕 Petr，试图在所有事情上模仿他。Alex 也设计了一个关于随机排列的问题。他像 Petr 一样生成随机排列，但交换元素的次数是 $7 n + 1$ 次，而不是 $3 n$ 次。因为这样更随机，对吧？！\n\n你偶然得到了一个来自上述两个问题之一的测试用例，现在你需要判断它来自哪一个。\n\n输入的第一行包含一个整数 $n$（$10^3 lt.eq n lt.eq 10^6$）。\n\n第二行包含 $n$ 个介于 $1$ 到 $n$ 之间的互不相同的整数 —— 来自该测试用例的大小为 $n$ 的排列。\n\n保证除样例外的所有测试用例均按以下方式生成：首先选择排列的大小 $n$，然后随机选择一种生成排列的方法 —— Petr 的方法或 Alex 的方法，再使用选定的方法生成排列。\n\n如果测试用例是通过 Petr 的方法生成的，请输出 \"_Petr_\"（不含引号）；如果是通过 Alex 的方法生成的，请输出 \"_Um_nik_\"（不含引号）。\n\n请注意，样例不是合法的测试用例（因为 $n$ 的限制），仅用于说明输入/输出格式。你的程序*仍必须为该测试用例输出正确答案*才能通过。\n\n由于输入具有随机性，本题禁止进行 Hack。\n\n## Input\n\n在输入的第一行中有一个整数 $n$（$10^3 lt.eq n lt.eq 10^6$）。第二行有 $n$ 个介于 $1$ 和 $n$ 之间的互不相同的整数 —— 来自测试用例的大小为 $n$ 的排列。保证除样例外的所有测试用例均按以下方式生成：首先选择 $n$ —— 排列的大小，然后随机选择一种生成排列的方法 —— Petr 的方法或 Alex 的方法，再使用选定的方法生成排列。\n\n## Output\n\n如果测试用例是通过 Petr 的方法生成的，请输出 \"_Petr_\"（不含引号）；如果是通过 Alex 的方法生成的，请输出 \"_Um_nik_\"（不含引号）。\n\n[samples]\n\n## Note\n\n请注意，样例不是合法的测试用例（因为 $n$ 的限制），仅用于说明输入/输出格式。你的程序*仍必须为该测试用例输出正确答案*才能通过。由于输入具有随机性，本题禁止进行 Hack。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $\\sigma \\in S_n$ be the given permutation, initially the identity permutation $id = (1, 2, \\dots, n)$.\n\nPetr performs $3n$ random transpositions (swaps of two distinct elements).  \nAlex performs $7n + 1$ random transpositions.\n\nEach transposition changes the parity of the permutation.  \nThe identity permutation has even parity.  \nAfter $k$ transpositions, the parity of the resulting permutation is $k \\mod 2$.\n\nThus:\n- If $3n$ is even, then $\\sigma$ is even.\n- If $3n$ is odd, then $\\sigma$ is odd.\n- If $7n + 1$ is even, then $\\sigma$ is even.\n- If $7n + 1$ is odd, then $\\sigma$ is odd.\n\nCompute the parity of $\\sigma$ (i.e., the parity of the number of inversions, or equivalently, the sign of the permutation).\n\nCompute:\n- $p_1 = 3n \\mod 2$\n- $p_2 = (7n + 1) \\mod 2$\n\nThen:\n- If $\\text{parity}(\\sigma) = p_1$, output \"Petr\".\n- Else if $\\text{parity}(\\sigma) = p_2$, output \"Um_nik\".\n\nNote: Since $3n \\mod 2 = n \\mod 2$, and $7n + 1 \\mod 2 = n + 1 \\mod 2$, we have:\n- $p_1 = n \\mod 2$\n- $p_2 = (n + 1) \\mod 2$\n\nTherefore, the two methods produce permutations of opposite parities.\n\nHence:\n- If $\\sigma$ is even, then it was generated by Petr if $n$ is even, by Alex if $n$ is odd.\n- If $\\sigma$ is odd, then it was generated by Petr if $n$ is odd, by Alex if $n$ is even.\n\nIn other words:\n$$\n\\text{Output } \\begin{cases}\n\\text{\"Petr\"} & \\text{if } \\text{parity}(\\sigma) \\equiv n \\pmod{2} \\\\\n\\text{\"Um_nik\"} & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF987E","tags":["math"],"sample_group":[["5\n2 4 5 1 3","Petr"]],"created_at":"2026-03-03 11:00:39"}}