求解最大值
首先考虑如何求解第一问，即求出边数的最大值。容易观察到，单次操作改变的边数的奇偶性为 $\frac{(k-1)k}{2} \bmod 2$，且图中单个点的度数改变的奇偶性为 $(k-1) \bmod 2$。
可以推测，在 $2 \le k \le n-2$ 的限制下，仅需考虑全局边数奇偶性与各点度数奇偶性的约束，即可构造出所有可能得到的图。
以下给出一个非构造性的证明：
将该操作置于线性代数背景下考量。令 $x_{i,j} \in \{0,1\}$ 表示顶点 $i$ 与 $j$ 之间的边是否存在。 可将图的状态抽象为长度为 $\frac{n(n-1)}{2}$ 的向量 $\vec{x}$。显然所有可由初始空图通过操作变换而来的 $\vec{x}$ 张成了一个向量空间 $U$。
- 若 $k \equiv 0, 1 \pmod 4$，所有可达的 $\vec{x}$ 必然满足其内 $1$ 的个数具有一致的奇偶性。
- 若 $k$ 为奇数，所有可达的 $\vec{x}$ 必然满足每个点的度数奇偶性不变。
定义 $R$ 为仅考虑全局边数奇偶性约束和局部度数奇偶性约束下，满足要求的所有 $\vec{x}$ 张成的空间。
易知 $U \subseteq R$ 恒成立。若能进一步证明 $\dim U = \dim R$，则表明这两个空间完全重合，从而上述条件的充分性便得到证明。
首先计算 $\dim R$：
- 无约束时：$\dim R = \binom{n}{2}$。
- 仅受边数奇偶性限制时：$\dim R = \binom{n}{2} - 1$。
- 仅受点度数奇偶性限制时：此时增加了 $n$ 条方程，但注意到这 $n$ 条方程线性相关（由于每条边对总度数的贡献恒为偶数，这 $n$ 条方程的加和在模 $2$ 意义下恒为 $0$），因此 $\dim R = \binom{n}{2} - n + 1 = \binom{n-1}{2}$。
- 两种限制兼有时：$\dim R = \binom{n-1}{2} - 1$。
接下来计算 $\dim U$。计算一组合法基的秩相对困难，可转而利用对偶思想，计算其正交补空间 $U^\perp$ 的秩。
规定下述计算全在 $\mathbb{F}_2$ 域下进行。取标准内积： $$ \langle x, y \rangle = \bigoplus_{i < j} x_{i,j} y_{i,j} $$ 对于任意大小为 $k$ 的子集 $S$，定义 $\vec{v}(S)$ 为其对应的翻转边向量，则： $$ U^\perp = \{ y \mid \langle y, \vec{v}(S) \rangle = 0, \ \forall \ |S|=k \} $$ 此时有 $\dim U = \binom{n}{2} - \dim U^\perp$。
性质 1：满足条件的正交补向量 $y$，对于任意互异的四点 $a, b, c, d$ 均有 $y_{a,b} \oplus y_{c,d} \oplus y_{a,c} \oplus y_{b,d} = 0$ 成立。
证明： 由于 $2 \le k \le n-2$，在给定的互异四点 $a, b, c, d$ 之外，一定能选出包含其他 $k-2$ 个点的集合 $T$。考虑以下四个大小为 $k$ 的子集：$T \cup \{a,b\}, T \cup \{c,d\}, T \cup \{a,c\}, T \cup \{b,d\}$。由 $y \in U^\perp$ 可知，$y$ 与这四个子集对应的操作向量内积均为 $0$。将这四个内积结果取异或和，相互抵消后即留存 $y_{a,b} \oplus y_{c,d} \oplus y_{a,c} \oplus y_{b,d} = 0$，证毕。
性质 2：满足条件的正交补向量 $y$ 必具备形式 $y_{i,j} = r_i \oplus r_j \oplus c$。
证明： 对于任意互不相同的 $1, 2, i, j$ 运用性质 1，有 $y_{i,1} \oplus y_{2,j} \oplus y_{i,2} \oplus y_{1,j} = 0$。移项整理得 $y_{i,1} \oplus y_{i,2} = y_{1,j} \oplus y_{2,j}$。因此，存在常数 $t$ 使得 $y_{i,1} \oplus y_{i,2} = t$。令 $p_i = y_{i,1}$，$q_i = y_{i,2}$，则 $q_i = p_i \oplus t$。再次令 $(a,b,c,d) = (i,j,1,2)$ 代入性质 1，则：$y_{i,j} = p_i \oplus p_j \oplus t \oplus y_{1,2}$。令常数 $c = t \oplus y_{1,2}$，亦即形如 $y_{i,j} = p_i \oplus p_j \oplus c$，证毕。
将此通式代回正交条件进行分析。对任意大小为 $k$ 的集合 $S$，有： $$ \bigoplus_{i,j \in S, i < j} y_{i,j} = \bigoplus_{i,j \in S, i < j} (p_i \oplus p_j \oplus c) $$
先分析点权 $p$ 的贡献：
- 若 $k$ 为奇数，集合中包含每个点 $i$ 的连边数为 $k-1$，为偶数，故异或和恒为 $0$。
- 若 $k$ 为偶数，集合中包含每个点 $i$ 的连边数为 $k-1$，为奇数，故异或和为 $\bigoplus_{i \in S} p_i$。
再分析常数 $c$ 的贡献：
- 取决于子集边数 $\binom{k}{2}$ 的奇偶性，若为奇数则余 $c$，偶数则异或和为 $0$。
对 $k \bmod 4$ 分类讨论，此处以 $k \equiv 2 \pmod 4$ 为例说明（其余情况同理）：此时有 $(\bigoplus_{i \in S} p_i) \oplus c = 0$。选取任意两个仅相差一个不同元素的 $k$ 级集合 $T_1 = R \cup \{u\}$ 与 $T_2 = R \cup \{v\}$。将其代入上式取异或，可得 $p_u \oplus p_v = 0$，说明此时所有的 $p_i$ 均相等。复代入原式，因 $k$ 是偶数，必满足 $\bigoplus_{i \in S} p_i = 0$，故倒推得 $c = 0$。
回到原题，考虑从完全图中至少删除多少条边才能够满足要求。
- $k \equiv 0, 2 \pmod 4$ 的情况是简单的；
- $k \equiv 3 \pmod 4$ 的情况只需保持度数的奇偶性不变。由于与 $n-1$ 奇偶性不同的点必然有偶数个，只需简单地将其两两配对作为删去的边即可。
- $k \equiv 1 \pmod 4$ 的情况最为复杂，同时需要满足边数与度数限制。假设不满足度数奇偶性条件的点数为 $t$。首先进行配对，然后若边数的奇偶性依然不符，则当 $t > 0$ 时，可将某条删去的边 $(u,v)$ 修改为 $(u,x)$ 与 $(x,v)$，其中 $x$ 满足限制，只需多删除一条边。但如果不存在 $x$ 满足要求，则需要特殊构造，即删除 $(1, 2), (1, 3), (1, 4)$。当 $t = 0$ 时，可以额外删除形如 $(1,2), (2,3), (1,3)$ 的任一三角形。
$n \le 70$
有以下两种做法：
- 考虑不断随机一个操作方案并尝试加入线性基，直到构建出来 $U$。
- 任意给出一种不限制操作次数的方案，然后使用线性基即可得到不超过 $\binom{n}{2}$ 次操作的方案。
两种做法均可以使用 bitset 优化复杂度。
为了方便描述接下来的构造做法，以下将问题取反，变为将图的所有边全部删去。
$p = 2n ^ 2$
考虑一种操作：取任意四个互异顶点 $a,b,c,d$，以及不包含这些点的大小为 $k-2$ 的集合 $T$，做以下四种操作：$T\cup\{a,b\},T\cup\{c,d\},T\cup\{a,c\},T\cup\{b,d\}$。其恰好会反转 $ab,bd,dc,ca$ 四条边，也就是一个环。如果可以将原图分解为若干个环，那就得到了一种构造。
注意到只有当所有点的度数为偶数且边数为偶数时，可以分解为若干个环。对于不满足的情况，需要先进行类似求解最大值的调整操作。
接下来给出一种操作次数为 $2n^2$ 级别的构造方案：
令 $U=\{1,2,3,\dots,n-3\}$，$A=n-2$，$B=n-1$，$C=n$。考虑先将 $U$ 中的边删除：对于一条边 $(u,v)$，分解为环 $u-v-A-B$。则最后只会有 $A,B,C$ 与其他点右边以及自身内部有边。由于每个点的度数都为偶数，所以对于 $u\in U$，其与 $A,B,C$ 中有 $0/2$ 条边，如果有 $2$ 条边，那么只需要分解为一个环即可。由于边数为偶数，最后 $A, B, C$ 三个点中只会剩下 $0$ 条边，即所有边都会被删除。操作次数不超过 $4(n+\binom{n-3}{2})$。
$p = n ^ 2$
进一步地，每次可以消除两条边，即对于一个点 $u$，取出其相邻的两个邻居 $x,y$，然后分解为环 $A/B/C-x-u-y$ 即可。
这一做法可以使用随机化进行优化。具体地，可以先随机进行 $\dfrac{\binom{n}{2}}{\binom{k}{2}}$ 次操作将图预先打乱成随机图，然后贪心地消边，即尽可能先消除三元环，否则尽可能消除长度为 $3$ 的链。经过一定优化后可以通过本题。
$k \le 70$
考虑先将图消成只有后 $k + 2$ 个点之间有边。
从左往右依次考虑每个点 $u$，如果其度数为偶数，取出其两个邻居 $a,b$，然后做 $R\cup\{u,a\},R\cup\{u,b\}$ 两次操作，其中 $R$ 为一个大小为 $k-2$ 的公共集合且 $R$ 中不包含 $1\sim u-1$，这恰好翻转了 $R\cup\{u\}$ 与 $a,b$ 之间的边。如果其度数为奇数，需要先进行一次处理：若点 $u$ 的邻居个数 $\le k-1$，则包含其所有邻居然后任意补全，否则任意选出 $k-1$ 个邻居即可，然后接着使用上面的做法去消除。此时总次数为 $\binom{n}{2}-\binom{k+2}{2}$。
接下来直接使用线性基求解即可，时间复杂度为 $O(k ^ 6 / w)$。
$p = \binom{n}{2}$
首先仍然将其消除到只有 $k + 2$ 个点之间有边。
注意到 $k+2$ 个点的操作种类数为 $\binom{k+2}{2}$，与其基的个数十分接近。此时一次操作选 $k=n−2$ 个点，等价于排除两个点 $\{i,j\}$，翻转所有不接触 $i$ 或 $j$ 的边。把这次操作记为 $F_{i,j}$。设 $m$ 表示当前的边条数，$v_{i,j}$ 表示这条边是否存在，$x_{i,j}$ 表示是否操作 $F_{i,j}$，则以下方案是一种可行的构造：
$$ x_{i,j}=m\oplus deg_i\oplus deg_j\oplus v_{i,j}. $$
证明： 令 $A$ 为相交矩阵，表示完全图中第 $i$ 条边与第 $j$ 条边是否相交，那么有 $A\vec{x}$ 表示一条边被翻转的次数。令 $B$ 为当前图中的边向量，则只需证明 $B\oplus A\vec{x}=0$ 即可。而上述 $\vec{x}$ 的实际含义取的是 $x=AB$，即图中与其不相交的边的个数，故等价于证明 $B\oplus A^2B=0$。通过分类讨论可以计算得出（记 $J$ 为全 $1$ 矩阵）： $$ A^2=(n-3)I-(n-4)A+\binom{n-3}{2}J. $$
再次分类讨论即可证明 $B\oplus A^2B=0$。