我们已知 \(n\) 对夫妻的婚姻状况，称第 \(i\) 对夫妻的男方为 \(B_i\)，女方为 \(G_i\)。若某男 \(B_i\) 与某女 \(G_j\) 曾经交往过（无论是大学，高中，亦或是幼儿园阶段，\(i \le j\)），则当某方与其配偶（即 \(B_i\) 与 \(G_i\)或 \(B_j\) 与 \(G_j\)）感情出现问题时，他们有私奔的可能性。不妨设 \(B_i\) 和其配偶 \(G_i\) 感情不和，于是 \(B_i\) 和 \(G_j\) 旧情复燃，进而 \(B_j\) 因被戴绿帽而感到不爽，联系上了他的初恋情人 \(G_k\)……一串串的离婚事件像多米诺骨牌一般接踵而至。若在 \(B_i\) 和 \(G_i\) 离婚的前提下，这 \(2n\) 个人最终依然能够结合成 \(n\) 对情侣，那么我们称婚姻 \(i\) 为不安全的，否则婚姻 \(i\) 就是安全的。
给定所需信息，你的任务是判断每对婚姻是否安全。
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 \(B\) 在 \(A\) 学校的分发列表中，\(A\) 也不一定在 \(B\) 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
鸽了好久
强连通图：指的是一张有向图，其中从任意一个节点出发，都可达到该图的所有节点。
强连通分量：指的是有向图的一种子图，满足该子图为强连通图，且这个子图是 极大 的，即对于一幅图 \(G\) 的强连通分量 \(G_0\)，我们无法找到一副子图 \(G_1\) 为强连通图，且满足 \(G_0 \subsetneqq G_1 \subseteq G\)
对于该题，你需要展开 #define 宏定义。本题中的宏定义与
C++ 中的宏定义大致相同，不过有下列特点：
#undef 取消宏定义；#define a b+e，#define b c+d，对于
a 最终展开结果为 c+d+e；#define a b+c，#define b a+a，对于
b 的展开结果即为 b+c+b+c。其他细节详见题面。
将一个 \(8 \times 8\) 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的两部分中的任意一块继续如此分割，这样割了 \(n - 1\) 次后，连同最后剩下的矩形棋盘共有 \(n\) 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 \(n\) 块矩形棋盘，并使各矩形棋盘总分的平方和最小。
请编程对给出的棋盘及 \(n\) ，求出平方和的最小值。
数据范围：\(1 \leq n \leq 15\)
司令部的将军们打算在 \(N \times M\) 的网格地图上部署他们的炮兵部队。一个 \(N \times M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
数据范围：\(N \leq 100\)，\(M \leq 10\)
有一个球形空间产生器能够在 \(n\) 维空间中产生一个坚硬的球体。现在，你被困在了这个 \(n\) 维球体中，你只知道球面上 \(n + 1\) 个点的坐标，你需要以最快的速度确定这个 \(n\) 维球体的球心坐标，以便于摧毁这个球形空间产生器。
已知 \(n\) 元线性一次方程组。
\[ \begin{cases} a_{1, 1} x_1 + a_{1, 2} x_2 + \cdots + a_{1, n} x_n = b_1 \\ a_{2, 1} x_1 + a_{2, 2} x_2 + \cdots + a_{2, n} x_n = b_2 \\ \cdots \\ a_{n,1} x_1 + a_{n, 2} x_2 + \cdots + a_{n, n} x_n = b_n \end{cases} \]
请根据输入的数据，编程输出方程组的解的情况。
Kri 喜欢玩数字游戏。
一天，他在草稿纸上写下了 \(t\) 对正整数 \((x, y)\)，并对于每一对正整数计算出了 \(z = xy \gcd(x, y)\)。
可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 \(y\) 都擦除了，还可能改动了一些 \(z\)。
现在 Kri 想请你帮忙还原每一组的 \(y\)，具体地，对于每一组中的 \(x\) 和 \(z\)，你需要输出最小的正整数 \(z\)，使得 \(z = xy \gcd(x, y)\)。如果这样的 \(y\) 不存在，也就是 Zay 一定改动了 \(z\)，那么请输出 \(-1\)。
数据范围：\(1 \le t \le 5 \times {10}^5\)，\(1 \le x \le {10}^9\)，\(1 \le z < 2^{63}\)。
纪念一下这个 爆炸 的考试
晚上考完数学考试就到机房刷题。写了几道状压 DP。没过多久就下课了。然后回寝睡觉。
早上起来后看了一下 DP 题，感觉没啥做的，就看了会儿 B 站
然后发现鸽子 Alan Becker 居然更新了。
没过多久就开始考试，提前开网页，题目加载出来后把题面扔在了我们学校的 OI 群里。