{"problem":{"name":"D. Transfer Window","description":{"content":"You play a football manager. There are n football players in the game, and k of them — a1, a2, ..., ak — are currently playing in your team. You want players b1, b2, ..., bk to play in your team. To a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10175D"},"statements":[{"statement_type":"Markdown","content":"You play a football manager. There are n football players in the game, and k of them — a1, a2, ..., ak — are currently playing in your team. You want players b1, b2, ..., bk to play in your team. To achieve that, you can suggest other teams to exchange one of your players to their player.\n\nFor each ordered pair of distinct players (x, y) it is known whether or not a team controlled by AI would accept to exchange your player x to their player y. Determine whether it is possible to collect a team consisting of football players b1, b2, ..., bk and if it is, output the order of exchanges to achieve it.\n\nThe first line contains two integers n and k (1 ≤ n ≤ 300, 1 ≤ k ≤ n) — the total number of football players in the game and the number of football players in your team.\n\nThe second line contains k distinct integers ai (1 ≤ ai ≤ n) — the players currently playing in your team.\n\nThe third line contains k distinct integers bi (1 ≤ bi ≤ n) — the players you want to see in your team.\n\nEach of the next n lines contains n characters. Character in i-th line and j-th column equals «_1_», if the team controlled by AI would accept to exchange your player i to their player j, and «_0_», if it wouldn't. Characters on the main diagonal are equal to zero.\n\nIn the first line output «_YES_», if it's possible to make a team of players b1, b2,  ..., bk, and «_NO_», if it's not.\n\nIn the case of the «_YES_» answer, in the second line output a single integer q (0 ≤ q ≤ n·n) — the number of exchanges, and then q lines — the sequence of exchanges. Each of these q lines must contain two distinct integers xj and yj (1 ≤ xj ≤ n, 1 ≤ yj ≤ n) — the number of player from your team you want to exchange and the number of player from another team you want to get for him. Please note that after j-th exchange player yj becomes a player of your team and player xj leaves your team.\n\nIf there are several sequences of exchanges leading to the desired result, output any of them. Also note that it's not required to minimize the number of exchanges, it's just enough if it doesn't exceed n·n.\n\n## Input\n\nThe first line contains two integers n and k (1 ≤ n ≤ 300, 1 ≤ k ≤ n) — the total number of football players in the game and the number of football players in your team.The second line contains k distinct integers ai (1 ≤ ai ≤ n) — the players currently playing in your team.The third line contains k distinct integers bi (1 ≤ bi ≤ n) — the players you want to see in your team.Each of the next n lines contains n characters. Character in i-th line and j-th column equals «_1_», if the team controlled by AI would accept to exchange your player i to their player j, and «_0_», if it wouldn't. Characters on the main diagonal are equal to zero.\n\n## Output\n\nIn the first line output «_YES_», if it's possible to make a team of players b1, b2,  ..., bk, and «_NO_», if it's not.In the case of the «_YES_» answer, in the second line output a single integer q (0 ≤ q ≤ n·n) — the number of exchanges, and then q lines — the sequence of exchanges. Each of these q lines must contain two distinct integers xj and yj (1 ≤ xj ≤ n, 1 ≤ yj ≤ n) — the number of player from your team you want to exchange and the number of player from another team you want to get for him. Please note that after j-th exchange player yj becomes a player of your team and player xj leaves your team.If there are several sequences of exchanges leading to the desired result, output any of them. Also note that it's not required to minimize the number of exchanges, it's just enough if it doesn't exceed n·n.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n $.  \nLet $ A = \\{a_1, \\dots, a_k\\} \\subseteq \\{1, \\dots, n\\} $ be the set of current players in your team.  \nLet $ B = \\{b_1, \\dots, b_k\\} \\subseteq \\{1, \\dots, n\\} $ be the target set of players.  \nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, \\dots, n\\} $, and an edge $ (x, y) \\in E $ iff the AI accepts exchanging your player $ x $ for player $ y $, represented by a binary adjacency matrix $ M \\in \\{0,1\\}^{n \\times n} $ where $ M_{x,y} = 1 $ iff exchange $ x \\to y $ is allowed.\n\n**Constraints**  \n1. $ A \\cap B \\subseteq \\{1, \\dots, n\\} $, $ |A| = |B| = k $.  \n2. $ M_{x,x} = 0 $ for all $ x \\in \\{1, \\dots, n\\} $.  \n3. Only exchanges involving your current team members (in $ A $) and external players (in $ \\{1, \\dots, n\\} \\setminus A $) are valid.  \n4. After each exchange, your team updates: remove $ x $, add $ y $.  \n5. The number of exchanges $ q \\leq n^2 $.\n\n**Objective**  \nDetermine whether there exists a sequence of exchanges transforming $ A $ into $ B $, using only allowed edges $ (x, y) \\in E $, where $ x \\in A $ (current team) and $ y \\notin A $ (external).  \nIf possible, output any valid sequence of $ q $ exchanges $ (x_j, y_j) $ such that after all exchanges, the team equals $ B $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10175D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}