{"problem":{"name":"K. Kleptography","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10248K"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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. \n\n## Output\n\nOutput the plaintext of John's diary.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10248K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}