给定一个 $n$ 个点，$m$ 条边的无向联通图，每条边的权值均为 $a$。

在原图所有满足 $u$ 节点和 $v$ 节点间最短路为 $2 \times a$ 的点对 $(u,v)$ 间建立一条无向边，边的权值均为 $b$。

给定一个起始节点$k$，求在上述操作后，$k$到所有节点的最短路径。

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

HH 是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 $1$ ），问长度为 $t$ ，从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合上述条件的路径。

定义一棵树上最长的路径为树的直径。树的直径可能不唯一。

给定的一棵 $n$ 个结点的树，求其直径的长度，以及有多少条边满足所有的直径都经过该边。

美食节共有 $n$ 种不同的菜品，每个同学都点了一份在这 $n$ 个菜品中的菜。总共有 $m$ 个厨师来制作这些菜品。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。第 $j$ 个厨师制作第 $i$ 种菜品的时间记为 $t _ {i,j}$ 。每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。总等待时间为所有同学的等待时间之和。

已知共有 $n$ 种菜品，第 $i$ 种菜品需要做 $p_i$ 份，共有 $m$ 个厨师。请计算出最小的总等待时间是多少。

lxhgww 最近迷上了一款游戏，在游戏里，他拥有 $n$ 个装备（ $n \le 1000000$ ），每种装备都有 $2$ 个属性，这些属性的值用 $[1,10000]$ 之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。

游戏进行到最后， lxhgww 遇到了终极 boss ，这个终极 boss 很奇怪，攻击他的装备所使用的属性值必须从 $1$ 开始连续递增地攻击，才能对 boss 产生伤害。现在lxhgww想知道他最多能连续攻击 boss 多少次？

有一个 $n$ 行 $m$ 列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m _ {i,j}$ 次交换。

输出仅一行，为最小交换总次数。如果无解，输出 $-1$ 。

你的公司需要提供 $n$ 类产品，其中第 $i$ 类产品共需要 $C _ {i}$ 件。公司共有 $m$ 名员工。员工能够制造的产品种类有所区别，我们用一个由 $0$ 和 $1$ 组成的 $m\times n$ 的矩阵 $\mathbb {A}$ 来描述每名员工能够制造哪些产品。

对于员工 $i$ ，给出 $S_i$ 。定义他的愤怒值与他制作的产品数量之间的函数是一个 $S_i+1$ 段的分段函数。设 $T _ {i,0}=0$,$T _ {i,S _ {i+1}}=+\infty$ ，那么当他制造第 $[T _ {i,j-1}+1,T _ {i,j}]$ 件产品时，每件产品会使他的愤怒值增加 $W _ {i,j}$ ， $1\leq j\leq S _ {i+1}$ 。保证 $0\lt W _ {i,j} \lt W _ {i,j+1}, \; 0 \lt T _ {i,j} \lt T _ {i,j+1}$ 。

你的任务是制定出一个产品的分配方案，使得订单条件被满足，并且所有员工的愤怒值之和最小。

给定一张有向图，每条边都有一个容量 $C$ 和一个扩容费用 $W$ 。这里扩容费用是指将容量扩大 $1$ 所需的费用。

现在请你编写一个程序求出：

1. 在不扩容的情况下， $1$ 到 $N$ 的最大流；
2. 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。

给定一个有向图 $G$ ，请求出 $G$ 的最大半连通子图拥有的节点数 $K$ ，以及不同的最大半连通子图的数目 $C$ 。