E. Numbers Exchange

Eugeny 有 #cf_span[n] 张卡片，每张卡片上恰好写有一个整数。Eugeny 希望与 Nikolay 交换一些卡片，使得他手中的偶数个数等于奇数个数，且所有这些数互不相同。 Nikolay 有 #cf_span[m] 张卡片，上面分别写有从 #cf_span[1] 到 #cf_span[m] 的互不相同的整数，每张卡片一个数。这意味着 Nikolay 恰好有一张写有数字 #cf_span[1] 的卡片、一张写有数字 #cf_span[2] 的卡片，依此类推。 一次交换是指 Eugeny 给 Nikolay 一张卡片，并从 Nikolay 那里拿回另一张卡片。你的任务是找出最少的交换次数，并确定 Eugeny 应该交换哪些卡片。 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2·105]，#cf_span[1 ≤ m ≤ 109]）——分别表示 Eugeny 和 Nikolay 的卡片数量。保证 #cf_span[n] 为偶数。 第二行包含一个长度为 #cf_span[n] 的正整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——表示 Eugeny 卡片上的数字。 如果无解，请输出 _-1_。 否则，第一行输出最少交换次数。第二行输出 #cf_span[n] 个整数——表示所有交换完成后 Eugeny 手中的卡片。卡片的顺序应与输入数据中的顺序一致。如果第 #cf_span[i] 张卡片未被交换，则第 #cf_span[i] 个数应与输入数据中的数相同；否则，认为该卡片已被交换，第 #cf_span[i] 个数应为交换后获得的卡片上的数字。 如果有多个答案，允许输出任意一个。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2·105]，#cf_span[1 ≤ m ≤ 109]）——分别表示 Eugeny 和 Nikolay 的卡片数量。保证 #cf_span[n] 为偶数。第二行包含一个长度为 #cf_span[n] 的正整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——表示 Eugeny 卡片上的数字。 ## Output 如果无解，请输出 _-1_。否则，第一行输出最少交换次数。第二行输出 #cf_span[n] 个整数——表示所有交换完成后 Eugeny 手中的卡片。卡片的顺序应与输入数据中的顺序一致。如果第 #cf_span[i] 张卡片未被交换，则第 #cf_span[i] 个数应与输入数据中的数相同；否则，认为该卡片已被交换，第 #cf_span[i] 个数应为交换后获得的卡片上的数字。如果有多个答案，允许输出任意一个。 [samples]

**Definitions:** - Let $ A = \{a_1, a_2, \dots, a_n\} $ be the multiset of integers on Eugeny’s cards. - Let $ B = \{1, 2, \dots, m\} $ be the set of integers on Nikolay’s cards. - Let $ E_A $ be the number of even integers in $ A $. - Let $ O_A $ be the number of odd integers in $ A $. Since $ n $ is even, $ E_A + O_A = n $. - Let $ E_B $ be the number of even integers in $ B $: $ E_B = \left\lfloor \frac{m}{2} \right\rfloor $. - Let $ O_B $ be the number of odd integers in $ B $: $ O_B = \left\lceil \frac{m}{2} \right\rceil $. **Constraints:** - After exchanges, Eugeny must have exactly $ \frac{n}{2} $ even and $ \frac{n}{2} $ odd integers. - All $ n $ integers on Eugeny’s final cards must be **distinct**. - Each exchange: Eugeny gives one card from $ A $, receives one card from $ B $, and the received card must not already be in his final set. - Nikolay’s cards are all distinct and in $ [1, m] $, and each card can be used at most once. **Objective:** Find the **minimum number of exchanges** $ k $, and a resulting multiset $ A' $ of $ n $ distinct integers such that: - $ |\{x \in A' : x \text{ even}\}| = \frac{n}{2} $, - $ |\{x \in A' : x \text{ odd}\}| = \frac{n}{2} $, - $ A' $ is obtained by replacing $ k $ elements of $ A $ with $ k $ distinct elements from $ B \setminus A $, - $ k $ is minimized. **Formal Problem Statement:** Let $ A = \{a_1, \dots, a_n\} $, $ B = \{1, 2, \dots, m\} $, $ n $ even. Define: - $ E_A = |\{a_i \in A : a_i \text{ even}\}| $, - $ O_A = |\{a_i \in A : a_i \text{ odd}\}| = n - E_A $. Let $ D_{\text{even}} = \frac{n}{2} - E_A $: number of even cards Eugeny needs to **gain** (if negative, he must **lose** even cards). Let $ D_{\text{odd}} = \frac{n}{2} - O_A $: number of odd cards Eugeny needs to **gain**. Note: $ D_{\text{even}} = -D_{\text{odd}} $, since $ E_A + O_A = n $. Let: - $ \text{even\_to\_remove} = \max(0, E_A - \frac{n}{2}) $: number of even cards in $ A $ that must be exchanged out. - $ \text{odd\_to\_remove} = \max(0, O_A - \frac{n}{2}) $: number of odd cards in $ A $ that must be exchanged out. - $ \text{even\_to\_add} = \max(0, \frac{n}{2} - E_A) $: number of even cards from $ B \setminus A $ to add. - $ \text{odd\_to\_add} = \max(0, \frac{n}{2} - O_A) $: number of odd cards from $ B \setminus A $ to add. **Feasibility Conditions:** 1. $ \text{even\_to\_add} \leq E_B - |\{x \in A : x \text{ even}\}| $ — enough even numbers available in $ B $ not already in $ A $. 2. $ \text{odd\_to\_add} \leq O_B - |\{x \in A : x \text{ odd}\}| $ — enough odd numbers available in $ B $ not already in $ A $. If either condition fails, output **-1**. **Minimum number of exchanges:** $ k = \text{even\_to\_remove} + \text{odd\_to\_remove} = \text{even\_to\_add} + \text{odd\_to\_add} $ **Output:** Construct $ A' $ as follows: - For each card $ a_i $ in original $ A $: - If $ a_i $ is even and $ \text{even\_to\_remove} > 0 $, and we still need to remove even cards, replace $ a_i $ with the next available even number from $ B \setminus A $ (in increasing order, for determinism). - If $ a_i $ is odd and $ \text{odd\_to\_remove} > 0 $, and we still need to remove odd cards, replace $ a_i $ with the next available odd number from $ B \setminus A $. - Otherwise, leave $ a_i $ unchanged. Ensure replacements are distinct and from $ B \setminus A $, and total replacements = $ k $. **Final Formal Output:** Given $ n, m, A = [a_1, \dots, a_n] $: - Compute $ E_A, O_A $. - Compute required changes: $ \Delta_e = \frac{n}{2} - E_A $, $ \Delta_o = \frac{n}{2} - O_A $. - Let $ S_e = \{ x \in B \setminus A : x \text{ even} \} $, $ S_o = \{ x \in B \setminus A : x \text{ odd} \} $. - If $ |S_e| < \max(0, \Delta_e) $ or $ |S_o| < \max(0, \Delta_o) $, output **-1**. - Else, $ k = \max(0, -\Delta_e) + \max(0, -\Delta_o) = |\Delta_e| $ (since $ \Delta_e = -\Delta_o $). - Construct $ A' $: For each $ i \in [1, n] $: - If $ a_i $ is even and $ \Delta_e < 0 $ and we still need to remove even cards → replace with next from $ S_e $, remove that element from $ S_e $. - Else if $ a_i $ is odd and $ \Delta_o < 0 $ and we still need to remove odd cards → replace with next from $ S_o $, remove that element from $ S_o $. - Else → keep $ a_i $. - Output $ k $, then $ A' $. **Note:** $ B \setminus A $ is computable as the set difference between $ \{1, \dots, m\} $ and the set of values in $ A $. Since $ m $ can be up to $ 10^9 $, we must avoid constructing $ B $ explicitly; instead, we generate needed even/odd numbers on-demand from $ B \setminus A $ using sorted lists of missing values in ranges.