fork()==0世界线变动

给定长度为n（n为偶数）的数列x的偶数项，求出数列x的奇数项，使得对于任意t∈[1,n]，x1+x2+...+xt为平方数，若无解输出No，否则先输出一行Yes，再输出x1,x2,x3,...,xn，若有多解输出任意一组解。

$x$ 数组奇数项不超过 ${10}^{13}$，偶数项不超过 $2 \times {10}^5$，$n \le 10^5$。

在一棵树上删去一些边，使得形成的几个连通块，都有且仅有 $3$ 个结点。

第一行是数据组数，接下来：

对于每组数据：

• 第一行一个正整数 $n$，表示结点数量。

• 接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u,v$ 间有一条边。

对于每组数据：

• 若不存在任何一种删边方式满足条件，则输出：-1。

• 若存在满足条件的删边方式：

• 第一行，一个正整数，删掉的边数。

• 第二行，所有删掉的边的编号，若不用删除任何边，则输出一个空行。

by @gty314159

Treeland包含n个城市和n-1条道路。每条道路都是双向的，连接两个不同的城市。从任何一个城市你都可以通过公路到达任何其他城市。是的，你是对的——这个国家的拓扑结构是一棵没有方向的树。

在Treeland有一些私人道路公司。政府决定向这些公司出售道路。每条路都属于一家公司，一家公司可以拥有多条道路。

政府害怕看上去不公平。他们认为，如果有一家公司拥有两条或两条以上的进入这个城市的道路，那么这个城市里的人就会认为这是不公平的。政府希望这样不公平的城市数量不超过k，那么最少需要多少个不同的公司来参与投资？

选择公司的数量r，这样就可以将每条道路分配给某家公司，这样一家公司拥有两条或两条以上到达同一个城市道路的城市数量最多为k。（译者注：这里是有一点费脑子，大家多想想）换句话说，如果对一个城市来说，所有的到达这座城市的道路都属于不同的公司，那么这个城市就是好的。你的任务是找到最小的r，然后分配所有道路，使得不太好的城市的数量不超过k。

图为第一个例子(n=6，k=2)。答案r=2。边上的数字表示边的编号。边的颜色表示公司：红色为第一个公司，蓝色为第二个公司。灰色顶点(3号)不好。这类顶点的数目(只有一个)不超过k（k=2）。如果有一家公司，在分配合理的情况下，不可能有2个不好的城市。

有$q$组询问,每组询问如下:

已知一个有$n(3\le n\le 210^5)$个点的环,点$i$的类型为$a_i$,现在需要给每个点进行染色,要求相邻*不同类型的点的颜色不同且所用颜色数最小.输出颜色数及一种染色方案即可.(颜色从1开始)

注意:($\sum n)\le 2*10^5$.

**简易版和繁难版的唯一区别是，简易版中的给定字符串 $s$ 最初是一个回文字符串，而繁难版中的这一条件并不总是正确的。

回文字符串是指从左到右和从右到左读法相同的字符串。例如，"101101 "是一个回文字符串，而 "0101 "不是。

爱丽丝和鲍勃正在一个长度为 $n$ 的字符串 $s$ 上玩游戏，这个字符串由字符 "0 "和 "1 "组成。双方轮流玩，爱丽丝先玩。

在每个回合中，玩家可以执行以下操作之一：

1. 选择任意 $i$ ( $1 \le i \le n$ )，其中 $s[i] =$ 为'0'，并将 $s[i]$ 改为'1'。0"，并将 $s[i]$ 改为 "1"。支付 1 美元。

2. 反转整个字符串，支付 0 美元。只有当字符串目前***不是回文字符串，并且上一次操作不是反转时，才允许进行此操作。也就是说，如果爱丽丝反转了字符串，那么鲍勃下一步就不能反转，反之亦然。

反转字符串是指将字符串中的字母从最后一个重新排序到第一个。例如，"01001 "在反转后会变成 "10010"。

当字符串中的每个字符都变成 "1 "时，游戏结束。到此为止，花费最少的玩家获胜，如果双方花费相同，则为平局。如果双方都以最佳方式进行游戏，输出结果是 Alice 赢、Bob 赢还是平局。

有一个长为 $n$ 数列 $a$，值已确定且值互不相等，但是你不知道。

现在有个设备，你可以输入长为 $k$ 的上升序列 $p_1,p_2 \dots p_k$，进行询问，它会回答 $a_{p_1},a_{p_2} \dots a_{p_k}$ 中第 $m$ 小的数在原数列的坐标和这个数的值。现在给你 $n$ 和 $k$，让你在最多询问 $n$ 次后回答 $m$ 的大小。保证一定可以构造出方案。

已知对两个长度为 $N$ 的、可能未排序的数组 $A$ 和 $B$ 执行如下的归并操作，生成的数组是一个长度为 $2N$ 的、给定的排列（即 $[1,2N]$ 中每个整数都正好出现一遍的数组）$C$：

```

Merge(A[1..N], B[1..N]):

C = []

i = 1

j = 1

while i <= N AND j <= N:

if A[i] < B[j]:  append A[i] to C  i = i + 1else:  append B[j] to C  j = j + 1

while i <= N:

append A[i] to Ci = i + 1

while j <= N:

append B[j] to Cj = j + 1

return C

```

构造出任意一组符合条件的 $A,B$；如果无解输出 -1。

翻译自 @zyc212303。