那个夏天，大家在小镇的树荫下约定：一定要找到最适合的秘密基地。
小镇中有 $$$n$$$ 个地点，由 $$$n-1$$$ 条小路连接，任意两个地点之间都存在唯一一条简单路径。因此，这些地点和小路构成了一棵无根树，地点编号为 $$$1$$$ 到 $$$n$$$。
每天，大家会按照一个顺序依次来到小镇中的所有地点。这个顺序用一个长度为 $$$n$$$ 的排列 $$$a_1,a_2,\ldots,a_n$$$ 表示，其中 $$$a_i$$$ 表示第 $$$i$$$ 个被访问的地点。
如果选择地点 $$$r$$$ 作为秘密基地，就可以把整棵树以 $$$r$$$ 为根。此时，对于两个不同地点 $$$x,y$$$，如果 $$$x$$$ 位于从 $$$r$$$ 到 $$$y$$$ 的简单路径上，则称 $$$x$$$ 是 $$$y$$$ 的祖先。
大家认为，如果某个地点先被访问，而它的某个祖先后被访问，就会产生一次"暴露风险"。形式化地，对于一个秘密基地 $$$r$$$，定义危险度 $$$f_r(a)$$$ 为满足以下条件的二元组 $$$(i,j)$$$ 的数量：$$$1\le i \lt j\le n$$$，且在以 $$$r$$$ 为根时，$$$a_j$$$ 是 $$$a_i$$$ 的祖先。
也就是说，$$$f_r(a)$$$ 表示在当前访问顺序下，有多少对地点满足：后出现的地点是先出现地点的祖先。
可是，时间不断流逝，大家的计划也会发生变化。接下来有 $$$q$$$ 次操作，每次操作给定一个整数 $$$x$$$，表示交换访问顺序中相邻的两个地点 $$$a_x$$$ 和 $$$a_{x+1}$$$。
在所有操作前，以及每次操作后，你都需要重新选择一个最合适的秘密基地，使危险度尽可能小，并输出这个最小危险度。
第一行包含两个整数 $$$n,q$$$ ($$$1\le n,q\le 2\cdot 10^5$$$)，分别表示地点数量和操作次数。
第二行包含 $$$n$$$ 个整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$)，表示初始访问顺序。保证 $$$a_1,a_2,\ldots,a_n$$$ 是一个排列。
接下来 $$$n-1$$$ 行，每行包含两个整数 $$$u_i,v_i$$$ ($$$1\le u_i,v_i\le n$$$)，表示地点 $$$u_i$$$ 和地点 $$$v_i$$$ 之间有一条小路。保证给出的 $$$n-1$$$ 条小路构成一棵树。
接下来 $$$q$$$ 行，每行包含一个整数 $$$x_i$$$ ($$$1\le x_i \lt n$$$)，表示一次操作，需要交换 $$$a_{x_i}$$$ 和 $$$a_{x_i+1}$$$。
输出 $$$q+1$$$ 行。
第一行输出初始访问顺序对应的最小危险度。
之后第 $$$i$$$ 行输出第 $$$i-1$$$ 次操作后的最小危险度。
5 33 5 1 2 41 22 32 44 5241
3 3 4 4
对于字符串 $$$S$$$，$$$T$$$，定义 $$$S$$$ 的字典序小于 $$$T$$$ 当且仅当以下三者之一成立：
- $$$S$$$ 为空串（长度为 $$$0$$$），$$$T$$$ 为非空串；
- $$$S,T$$$ 为非空串，且 $$$S[0]$$$ 字典序小于 $$$T[0]$$$，这里 $$$S[0],T[0]$$$ 表示 $$$S,T$$$ 的首个字符；
- $$$S,T$$$ 为非空串，且 $$$S[0]=T[0]$$$，$$$S[1,\cdots]$$$ 字典序小于 $$$T[1,\cdots]$$$，这里 $$$S[1,\cdots],T[1,\cdots]$$$ 表示 $$$S,T$$$ 删除首个字符得到的字符串。
对于由 {'(',')'} 组成的括号串 $$$S$$$，称其为可匹配的，当且仅当以下三者之一成立：
- $$$S$$$ 是空串（长度为 $$$0$$$）；
- $$$S = (A)$$$，其中 $$$A$$$ 是可匹配的括号串；
- $$$S = AB$$$，其中 $$$A$$$，$$$B$$$ 都是可匹配的非空括号串。
下面给出一个可匹配的括号串 $$$T$$$，求有多少个括号串 $$$S$$$ 满足以下四个条件：
- $$$S$$$ 不是空串（长度大于 $$$0$$$）；
- $$$S$$$ 是可匹配的；
- $$$S=T$$$，或 $$$S$$$ 的字典序小于 $$$T$$$；
- $$$S$$$ 的长度小于等于 $$$T$$$ 的长度。
注意，符号 '(' 的字典序比 ')' 小。
本题采用多组测试。答案可能很大，请输出结果对 $$$998244353$$$ 取模后的余数。
每个测试点第一行包含一个正整数 $$$t$$$（$$$1 \le t \le 5\times 10^5$$$），表示数据组数。
接下来 $$$t$$$ 组数据，每组数据第一行为一个偶数 $$$n$$$（$$$2\le n\le 10^6$$$），表示字符串 $$$T$$$ 的长度。
第二行为一个长度为 $$$n$$$ 的括号串，其字符集为 {'(',')'}。这里保证 $$$T$$$ 是可匹配的。
保证单个测试点内所有括号串的长度总和不超过 $$$10^6$$$。
输出 $$$t$$$ 行，第 $$$i$$$ 行表示第 $$$i$$$ 组数据的答案对 $$$998244353$$$ 取模后的余数。
62()4()()4(())6()(())8(())(())20((()())(()())(()()))
1316117346
对于第四组数据，有以下六个符合要求的 $$$S$$$：
- ()
- (())
- ()(())
- (())()
- ((()))
- (()())
小 $$$z$$$ 爱玩洛克王国，尤其喜欢和别的玩家进行精灵对战。
现在有 $$$n$$$ 种精灵，编号为 $$$1$$$ 到 $$$n$$$。精灵之间存在克制关系。对于每种精灵，它最多被 $$$k$$$ 种精灵克制。
当小 $$$z$$$ 的精灵 $$$A$$$ 与对手的精灵 $$$B$$$ 对战时，结果如下：
- 若 $$$A$$$ 克制 $$$B$$$，且 $$$B$$$ 不克制 $$$A$$$，则 $$$B$$$ 被击倒，$$$A$$$ 继续战斗；
- 若 $$$B$$$ 克制 $$$A$$$，且 $$$A$$$ 不克制 $$$B$$$，则 $$$A$$$ 被击倒，$$$B$$$ 继续战斗；
- 若 $$$A$$$ 与 $$$B$$$ 之间不存在任何克制关系，则二者同归于尽；
- 若 $$$A$$$ 与 $$$B$$$ 互相克制，则小 $$$z$$$ 可以通过高超的博弈技巧击败对手的精灵，即 $$$B$$$ 被击倒，$$$A$$$ 继续战斗。
小 $$$z$$$ 已经提前知道了对手的精灵出战顺序，这是一个长度为 $$$m$$$ 的序列，序列中可以出现重复的精灵。
小 $$$z$$$ 需要合理安排自己的精灵出战顺序来击败对手的所有精灵。对战过程中，当前精灵没有被击倒时，不能更换精灵；只有当前精灵被击倒或同归于尽后，小 $$$z$$$ 才能派出新的精灵。小 $$$z$$$ 可以多次派出同一种精灵。
派出一只精灵需要花费 $$$1$$$ 的代价。请你求出小 $$$z$$$ 击败对手所有精灵所需的最小总花费。
第一行包含三个整数 $$$n,m,k$$$（$$$1 \le n,m \le 10^5, 1 \le k \le 30$$$），分别表示精灵种类数、对手精灵出战序列长度，以及每种精灵最多被克制的精灵种类数。
接下来 $$$n$$$ 行，第 $$$i$$$ 行首先包含一个整数 $$$s_i$$$（$$$0 \le s_i \le k$$$），表示克制第 $$$i$$$ 种精灵的精灵种类数；随后包含 $$$s_i$$$ 个整数 $$$x_{i,1},x_{i,2},\ldots,x_{i,s_i}$$$（$$$1 \le x_{i,j} \le n,x_{i,j} \neq i$$$），表示克制第 $$$i$$$ 种精灵的精灵编号。
最后一行包含 $$$m$$$ 个整数 $$$a_1,a_2,\ldots,a_m$$$（$$$1 \le a_i \le n$$$），表示对手的精灵出战序列。
输入保证每一行克制关系中的精灵编号互不相同，且不会出现自克制关系。
输出一行一个整数，表示小 $$$z$$$ 击败对手所有精灵所需的最小总花费。
3 4 21 22 3 11 12 2 2 1
1
一天，面码和仁太遇到了一个由小写英文字母组成的字符串 $$$s$$$。
为了打发时间，他们发明了一个游戏：面码可以任意重排字符串中所有奇数下标位置上的字符，仁太可以任意重排字符串中所有偶数下标位置上的字符。
他们想知道，经过这样的重排后，是否可以把字符串变成一个回文串$$$^{\text{∗}}$$$。请你帮助他们！
$$$^{\text{∗}}$$$回文串指从前往后读和从后往前读都相同的字符串。例如，$$$\mathtt{aa}$$$、$$$\mathtt{aba}$$$ 和 $$$\mathtt{abccba}$$$ 是回文串，而 $$$\mathtt{sccpc}$$$、$$$\mathtt{reality}$$$ 和 $$$\mathtt{ab}$$$ 不是回文串。
第一行包含一个整数 $$$t$$$（$$$1 \le t \le 100$$$），表示测试数据的组数。
对于每组测试数据，唯一一行包含一个由小写英文字母组成的字符串 $$$s$$$（$$$1 \le |s| \le 100$$$）。
对于每组测试数据，如果可以将 $$$s$$$ 变成回文串，输出一行 "YES"，否则输出一行 "NO"。
你可以以任意大小写形式输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被视为正确回答。
5abbaabcdaabbabcbaabcde
YESNOYESYESNO
在第一组测试数据中，给定字符串本身已经是一个回文串。
在第三组测试数据中，可以重排奇数下标位置，使得下标 $$$1$$$ 处为 $$$\mathtt{a}$$$，下标 $$$3$$$ 处为 $$$\mathtt{b}$$$；同时重排偶数下标位置，使得下标 $$$2$$$ 处为 $$$\mathtt{b}$$$，下标 $$$4$$$ 处为 $$$\mathtt{a}$$$。这样可以得到回文串 $$$\mathtt{abba}$$$。
有一棵 $$$n$$$ 个点的树 $$$T$$$，树的根节点为 $$$1$$$。初始时点 $$$i$$$ 有颜色 $$$c_i$$$（$$$0 \le c_i \le 1$$$）。
小 L 进行了若干次（可以为 $$$0$$$）操作，每次操作她会选择一个满足 $$$c_u =0$$$ 的节点 $$$u$$$，对 $$$u$$$ 子树内的所有点 $$$v$$$ 执行 $$$c_v \gets 1 - c_v$$$。所有操作结束后得到树 $$$T'$$$，其中点 $$$i$$$ 的颜色变为了 $$$c'_i$$$。
现在给你最后得到的树 $$$T'$$$ 和每个点的颜色 $$$c'_i$$$，你需要求出有多少种不同的可能初始状态 $$$T$$$。答案对 $$$998244353$$$ 取模。
在此题中，我们认为两棵树 $$$T_1,T_2$$$ 不同，当且仅当存在点 $$$1 \le u \le n$$$，满足其在 $$$T_1$$$ 中的颜色为 $$$c_{1,u}$$$，在 $$$T_2$$$ 中的颜色为 $$$c_{2,u}$$$，且 $$$c_{1,u} \neq c_{2,u}$$$。
输入第一行一个正整数 $$$n$$$（$$$1 \le n \le 2 \times 10^5$$$），表示 $$$T'$$$ 的点数。
第二行 $$$n$$$ 个整数 $$$c'_1,c'_2,\cdots,c'_n$$$（$$$0 \le c'_i \le 1$$$），表示最终状态下每个点的颜色。
接下来 $$$n-1$$$ 行，每行两个正整数 $$$u,v$$$（$$$1 \le u,v \le n$$$，$$$u \neq v$$$），表示 $$$T'$$$ 中存在一条边 $$$(u,v)$$$。保证所有边构成一棵树。
输出一行一个整数，表示可能的初始状态 $$$T$$$ 的个数对 $$$998244353$$$ 取模后的值。
30 0 11 21 3
2
51 0 0 1 11 21 32 42 5
20
给定一个长为 $$$n$$$ 的序列 $$$a$$$。判断是否存在序列 $$$b$$$ 满足：
- $$$S(a)=S(b)$$$，其中 $$$S(a)$$$、$$$S(b)$$$ 分别表示由序列 $$$a$$$ 和序列 $$$b$$$ 中所有元素构成的可重集；
- 不存在 $$$1 \le i \lt n$$$ 满足 $$$\gcd(b_1,\cdots,b_i) = \gcd(b_{i+1},\cdots,b_n)$$$。
本题有多组测试数据。
输入第一行一个正整数 $$$t$$$（$$$1 \le t \le 10$$$），表示数据组数。
每组数据中：
第一行一个正整数 $$$n$$$（$$$2 \le n \le 2 \times 10^5$$$），表示序列 $$$a$$$ 的长度。
第二行 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1 \le a_i \le 10^{12}$$$），表示序列 $$$a$$$。
保证 $$$\sum n \le 2 \times 10^5$$$。
对于每组数据：
若存在序列 $$$b$$$ 满足条件，输出一行 "YES"，否则输出一行 "NO"。
你可以以任意大小写形式输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被视为正确回答。
746 12 24 1552 4 3 9 662 3 5 4 9 2547 7 14 21210 2036 6 6514 21 22 33 17
YES YES NO NO YES NO YES
阿尔扎诺帝国魔术学院中，格伦老师难得认真地研究起了一本古老的禁忌教典。教典中记载了一种特殊的法术序列。序列由 $$$n$$$ 道咒文组成，第 $$$i$$$ 道咒文的魔力值为 $$$a_i$$$。
一开始，希丝缇娜以为只要把所有咒文的魔力简单相加，就能得到整个法术的强度。但格伦老师很快发现，这种咒文并不是这样运作的。第一道咒文会正向释放魔力，第二道咒文会反向抵消魔力，第三道咒文又会正向释放魔力，第四道咒文再次反向抵消魔力，之后依次交替。形式化地，对于一个法术序列 $$$b_1,b_2,...,b_m$$$，定义它的能量值为 $$$E(b)=\sum_{i=1}^{m}(-1)^{i+1}b_i$$$。空序列的能量值定义为 $$$0$$$。
在继续解析教典时，露米娅发现其中有一段连续咒文受到了异常魔力污染。如果直接吟唱，整个法术很可能会失控。于是格伦老师决定：必须恰好选择一段非空连续咒文，将它们从序列中抹去。也就是说，需要选择一个区间 $$$[l,r]$$$，删除 $$$a_l,a_{l+1},...,a_r$$$。被删除的咒文消失后，剩余咒文会按照原来的相对顺序自动连接成一个新的法术序列 $$$a_1,...,a_{l-1},a_{r+1},...,a_n$$$。
格伦老师希望最终得到的法术序列能量值恰好等于 $$$k$$$。请你帮助希丝缇娜和露米娅计算，有多少种不同的删除区间 $$$[l,r]$$$ 可以满足这个要求。
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$)，表示测试数据组数。
对于每组测试数据，第一行包含两个整数 $$$n,k$$$ ($$$1 \le n \le 10^6$$$，$$$-10^9 \le k \le 10^9$$$)，表示咒文数量和目标能量值。
第二行包含 $$$n$$$ 个整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)，表示每道咒文的魔力值。
保证所有测试数据的 $$$n$$$ 之和不超过 $$$10^6$$$。
对于每组测试数据，输出一个整数，表示满足要求的删除区间数量。
34 01 3 2 43 01 2 15 12 1 3 4 2
2 2 3
给定 $$$n$$$ 个点，每个点有一个整数权值 $$$W_i$$$。
定义两点 $$$i$$$ 和 $$$j$$$ 之间存在一条无向边，当且仅当 $$$W_i \oplus W_j$$$（其中 $$$\oplus$$$ 表示按位异或运算）的二进制表示中，$$$1$$$ 的个数为奇数。
请你求出这个图的最大权独立集。即，选择一个点集满足集合内任意两点之间没有边，且集合内点的权值之和最大。定义空集的权值为 $$$0$$$。你只需要求出这个最大的权值之和。
本题有多组数据。
输入一行一个正整数 $$$t$$$（$$$1 \le t \le 10^5$$$），表示测试数据组数。
每组数据中：
第一行一个正整数 $$$n$$$（$$$1 \le n \le 5 \times 10^5$$$），表示点数。
第二行 $$$n$$$ 个正整数 $$$W_1,W_2,\cdots,W_n$$$（$$$1 \le W_i \le 10^9$$$），表示点的权值。
保证 $$$1 \le \sum n \le 5 \times 10^5$$$。
每组数据输出一行一个整数，表示最大权独立集的权值之和。
353 5 15 1 236 7 1141 2 4 8
23 18 15
在某星系观测计划中，天文台记录了 $$$n$$$ 个恒星碎片在二维平面中的初始位置，其中第 $$$i$$$ 个碎片的位置为 $$$P_i(x_i,y_i)$$$。
受到中心引力源的影响，这些碎片会绕星系中心 $$$O(0,0)$$$ 以相同的角速度进行匀速旋转，且任意时刻所有点相对于原点的旋转角度相同。
天文台使用一个观测框对这些碎片进行持续观测，该观测框满足如下条件：
- 观测框为一个各边平行于坐标轴的矩形；
- 观测框必须完全覆盖所有碎片的位置；
- 观测框不必覆盖星系中心 $$$O(0,0)$$$；
- 在所有满足覆盖条件的观测框中，选取周长最小的那个。
随着时间的推移，碎片不断旋转，观测框的大小也随之变化，观测系统在该时刻的能量消耗速率与观测框的周长成正比。
为了合理估计观测系统的能量消耗，你打算通过观测框周长对能量消耗进行估计。随着观测时间的增加，观测框周长的平均值会趋于某个值，你的任务是计算这个值。
形式化地说：
设在某一时刻碎片系统绕 $$$O$$$ 点的旋转角度为 $$$\theta$$$，第 $$$i$$$ 个碎片的位置为 $$$(x_i',y_i')$$$，定义此时观测框的周长为： $$$$$$ P(\theta) = 2 \times \left(\max_{i=1}^n x_i' - \min_{i=1}^n x_i'\right) + 2\times \left(\max_{i=1}^n y_i' - \min_{i=1}^n y_i'\right) $$$$$$
你的任务是计算下面的值： $$$$$$ \lim_{T\to +\infty} \dfrac{1}{T} \int_{0}^T P(\theta) \mathrm{d}\theta $$$$$$
输入包含多组测试数据。
第一行包含一个整数 $$$t$$$（$$$1\le t\le 10^5$$$），表示测试数据的组数。
下面是 $$$t$$$ 组数据，对于每组测试数据：
第一行包含一个整数 $$$n$$$（$$$2 \le n \le 2 \times 10^5$$$），表示恒星碎片的数量。
接下来的 $$$n$$$ 行，每行包含两个整数 $$$x_i, y_i$$$（$$$-10^8 \le x_i, y_i \le 10^8$$$），表示第 $$$i$$$ 个恒星碎片的初始坐标 $$$P_i(x_i,y_i)$$$。保证单组数据内，碎片的坐标两两不同。
保证单个测试点内，所有测试数据的 $$$n$$$ 之和不超过 $$$2 \times 10^5$$$。
对于每组测试数据，输出一个实数，表示观测框周长的平均值。
注意，当你的答案与标准答案的相对误差或绝对误差不超过 $$$10^{-6}$$$ 时，视为正确。
620 01 040 00 20 30 530 01 00 150 01 02 03 14 -181 12 11 2-1 1-1 -12 -10 0-2 -23-100000000 100000000100000000 9876543212345678 100000000
2.54647908947012.7323954473524.34711172178512.12308827168416.470199993469509311738.569670943427
对于第一组数据，可以计算得出观测框周长期望值的精确数值为 $$$\frac{8}{\pi}$$$。
对于第二组数据，可以计算得出观测框周长期望值的精确数值为 $$$\frac{40}{\pi}$$$。
在一切都由游戏决定的世界中，史蒂芬妮、空和白正在研究一个新的棋盘游戏。
棋盘是一个 $$$2\times n$$$ 的矩阵。第 $$$i$$$ 行第 $$$j$$$ 列的格子中有 $$$a_{i,j}$$$ 枚硬币。
游戏开始时，玩家站在格子 $$$(1,1)$$$，目标是移动到格子 $$$(2,n)$$$。每一步只能向右移动一格，或者向下移动一格。
由于棋盘只有两行，所以一条合法路径等价于选择一个下移列 $$$k$$$：先从 $$$(1,1)$$$ 走到 $$$(1,k)$$$，再向下走到 $$$(2,k)$$$，最后走到 $$$(2,n)$$$。
白先行动，并收集自己路径上的所有硬币。白结束后，空再行动，并收集自己路径上所有没有被白经过的格子中的硬币。白想让空所收集到的硬币数量最小化，而空想让自己收集到的硬币最大化。
史蒂芬妮认真观察了一会儿，然后自信地提出了一个策略：白只要选择自己能拿到最多硬币的路径，不就赢了吗？
白沉默了一秒，指出这个策略并不一定正确。于是史蒂芬妮不服气地要求白立刻给出一个棋盘，使得她的策略会唯一地选择一条错误路径。可是白正在忙着和空博弈，于是把这个任务交给了你。
现在给你一个 $$$2\times n$$$ 的棋盘。棋盘中的一些位置已经给定为正整数，另一些位置为 $$$-1$$$。
你需要把所有 $$$-1$$$ 替换成 $$$[1,10^9]$$$ 内的正整数，使得构造后的棋盘满足以下条件：
存在唯一的路径，使得白拿到的硬币数量最大；并且史蒂芬妮的这个唯一选择是错误的，即存在另一种白的路径，使得空所能拿到的最大硬币数量更小。
如果无法构造这样的棋盘，输出 $$$-1$$$。
第一行包含一个整数 $$$n$$$（$$$1 \le n \le 2\cdot 10^5$$$），表示棋盘的列数。
第二行包含 $$$n$$$ 个整数 $$$a_{1,1},a_{1,2},\ldots,a_{1,n}$$$，表示棋盘的第一行。
第三行包含 $$$n$$$ 个整数 $$$a_{2,1},a_{2,2},\ldots,a_{2,n}$$$，表示棋盘的第二行。
对于每个位置，均满足 $$$a_{i,j}=-1$$$，或者 $$$1\le a_{i,j}\le 10^9$$$。
如果无法构造，输出一行一个整数 $$$-1$$$。
否则输出两行，每行 $$$n$$$ 个整数，表示构造后的棋盘。
3 5 -1 2 -1 2 7
5 1 2 2 2 7
1-11
-1
有一张无向连通简单图 $$$G$$$，它是一个基环树。也就是说，若 $$$G$$$ 有 $$$k$$$ 个点，则它恰好也有 $$$k$$$ 条边。
现在这张图发生了如下变异：
对于原图中的每个点 $$$x$$$，选择一个整数 $$$c_x \ge 3$$$，并将点 $$$x$$$ 替换成一个长度为 $$$c_x$$$ 的简单环 $$$C_x$$$。对于原图中的每一条边 $$$(u,v)$$$，在环 $$$C_u$$$ 上任选一个点，在环 $$$C_v$$$ 上任选一个点，并在这两个点之间连一条边。
不同的原边在同一个环上可以连接到同一个点，也可以连接到不同的点。保证变异后得到的图仍然是一个无向连通简单图。
现在给出变异后的图，你需要还原出任意一张与原图 $$$G$$$ 同构的基环树。
如果有多种答案，输出任意一种即可。
第一行一个正整数 $$$t$$$（$$$1 \le t \le 10^5$$$），表示数据组数。
对于每组数据：
第一行两个整数 $$$n,m$$$（$$$9 \le n \le 10^6,\ 12 \le m \le 10^6$$$），表示变异后图的点数和边数。
接下来 $$$m$$$ 行，每行两个整数 $$$u,v$$$（$$$1 \le u,v \le n,\ u \ne v$$$），表示变异后图中的一条无向边。
保证输入图是无向连通简单图，并且一定可以由某张基环树按照题目中的规则变异得到。
保证所有数据中，$$$\sum n \le 10^6,\ \sum m \le 1333333$$$。
对于每组数据：
第一行输出一个整数 $$$k$$$，表示你还原出的基环树的点数。
接下来输出 $$$k$$$ 行，每行两个整数 $$$u,v$$$，表示你还原出的基环树中的一条无向边。
你的输出图只要与某个合法原图同构即可，点的编号和边的顺序任意。
29 121 22 33 14 55 66 47 88 99 71 42 75 812 161 22 33 14 55 66 47 88 99 710 1111 1212 101 45 78 26 10
31 21 32 341 32 32 43 4
给定一个由小写英文字母组成的字符串 $$$S$$$，以及一个初始为空的字符串 $$$T$$$。
你需要对 $$$S$$$ 执行若干次操作，直到它变为空字符串。每次你可以执行以下三种操作中的一种：
- 删除 $$$S$$$ 的第一个字符，并将其添加到 $$$T$$$ 的末尾。
- 删除 $$$S$$$ 的最后一个字符，并将其添加到 $$$T$$$ 的末尾。
- 选择非空串 $$$A,B$$$ 满足 $$$S = ABA^R$$$，令 $$$S=B$$$ 并将字符串 $$$A$$$ 添加到 $$$T$$$ 的末尾。
其中 $$$A^R$$$ 表示字符串 $$$A$$$ 的反串。
求在所有操作方案中，能得到的字典序最小的 $$$T$$$。
本题有多组测试数据。
输入第一行一个正整数 $$$t$$$（$$$1 \le t \le 10^5$$$），表示测试数据组数。
每组测试数据：
输入一行一个由小写字母组成的字符串 $$$S$$$（$$$1 \le |S| \le 5 \times 10^5$$$）。
保证所有测试数据 $$$|S|$$$ 之和不超过 $$$5 \times 10^5$$$。
每组测试数据输出一行一个字符串表示答案。
6cbazayazaaaaaxazbxababaaa
abczaayaaaxabzaabaaa