{"raw_statement":[{"iden":"statement","content":"John likes simple ciphers. He had been using the \"Caesar\" cipher to encrypt his diary until recently, when he learned a hard lesson about its strength by catching his sister Mary browsing through the diary without any problems.\n\nRapidly searching for an alternative, John found a solution: the famous \"Autokey\" cipher. He uses a version that takes the $26$ lower-case letters '_a_'–'_z_' and internally translates them in alphabetical order to the numbers $0$ to $25$.\n\nThe encryption key $k$ begins with a secret prefix of $n$ letters. Each of the remaining letters of the key is copied from the letters of the plaintext $a$, so that $k_{n + i} = a_i$ for $i >= 1$. Encryption of the plaintext $a$ to the ciphertext $b$ follows the formula $b_i = a_i + k_i bmod 26$.\n\nMary is not easily discouraged. She was able to get a peek at the last $n$ letters John typed into his diary on the family computer before he noticed her, quickly encrypted the text document with a click, and left. This could be her chance.\n\nThe input consists of: \n\nOutput the plaintext of John's diary.\n\n"},{"iden":"input","content":"The input consists of:   One line with two integers $n$ and $m$ ($1 <= n <= 30$, $n + 1 <= m <= 100$), where $n$ is the length of the keyword as well as the number of letters Mary saw, and $m$ is the length of the text.  One line with $n$ lower-case letters, the last $n$ letters of the plaintext.  One line with $m$ lower-case letters, the whole ciphertext. "},{"iden":"output","content":"Output the plaintext of John's diary."},{"iden":"examples","content":"Input5 16\nagain\npirpumsemoystoal\nOutputmarywasnosyagain\nInput1 12\nd\nfzvfkdocukfu\nOutputshortkeyword\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected multigraph with:  \n- $ V = \\{0, 1, \\dots, n-1\\} $, the set of nodes,  \n- $ E $, the multiset of fiber links (edges), with $ |E| = m $.  \n\nLet $ d_G(v) $ denote the degree of node $ v $ in $ G $.  \n\nLet $ T = (V, E') $ be a spanning tree of $ G $, i.e., a connected acyclic subgraph with $ |E'| = n - 1 $.  \n\nLet $ d_T(v) $ denote the degree of node $ v $ in $ T $.  \n\n**Constraints**  \n1. $ 2 \\le n \\le 10^4 $  \n2. $ 1 \\le m \\le 10^5 $  \n3. $ G $ is connected (possibly with multiple edges).  \n4. $ T $ must be a spanning tree of $ G $.  \n\n**Objective**  \nMinimize the number of nodes $ v \\in V $ for which $ d_T(v) \\ne d_G(v) $.  \n\nOutput:  \n- The minimal number of such mismatched nodes.  \n- Any spanning tree $ T $ achieving this minimum, represented as a list of $ n-1 $ edges.","simple_statement":"You are given a connected network of n nodes and m fiber links. You must replace it with a new network using only wireless links, such that:\n\n- There is exactly one path between any two nodes (i.e., the new network is a tree).\n- Use as few wireless links as possible (so the tree has exactly n-1 links).\n- Minimize the number of nodes whose number of connections (degree) changes from the original network.\n\nOutput:\n1. The minimum number of nodes that must change their degree.\n2. Then, output the new tree: first line has n and n-1, then n-1 lines with the wireless links (any valid tree is accepted).","has_page_source":false}