代码如诗

有$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。

有T组数据

给出一个像国际象棋一样黑白染色的图，点 $(1,1)$ 为白色。

Tips: 其实就是如果点坐标是 $(x,y)$，$x+y$ 为偶时是白色，$x+y$ 为奇时是黑色。

你需要构造连通的含有b个黑点,w个白点的图。

如果无法构造，输出"NO"。

否则，输出"YES"，并在第2~(w+b+1)行输出构造方法，方式是“x y”，表示图上有点坐标为(x,y).

对于一棵有根树，定义一个节点 $i$ 是叶子结点，仅当 $i$ 没有子节点。进一步定义一个节点 $i$ 是“可移动节点”，仅当 $i$ 不是根、不是叶子节点且其所有直接相连的子节点都是叶子结点。

你可以对任意“可移动节点” $i$ 进行下列操作任意次：

• 断开 $i$ 与其父亲节点的边，选择任意一个不属于节点 $i$ 及其子树的节点 $j$ 并在 $i,j$ 之间连边。

给定一棵以节点 $1$ 为根的 $n$ 个节点的有根树，求经过若干次操作后，这棵树最少有几个叶子结点。$T$ 组数据。

保证：

$1\leq T\leq10^4;1\leq n,\sum n\leq2\times10^5;$

给定的是棵树。

给你一串字符串

你可以给字符串的每个位置染上 $0/1$

对于相邻的两个位置，如果他们的颜色不同则可以交换他们的位置

现在需要交换若干次后按照字典序升序排序

如果存在，请输出 $YES$ 并且输出一个可行的颜色序列

否则输出 $NO$