"良"，意为"善"也。"善"字形如开口的羊羔，若是人如羊羔一般温顺，便配得上"良"这名字。
然而，我并不觉得自己是羊。
崇祯元年（1628年），舌头是与良同行的另一头狼，两人分工明确，舌头引人，良出力，劫掠山路上的"羊"，靠"羊毛"度日。
并且，良有一个习惯，每宰一只"羊"都要留些"羊毛"带在身上。
这天，两人劫了一只"羊"，从他身上拿了五两银、二百余钱，一身破衣，一个荷包等。
良把荷包带在了身上，随后两人继续合计怎么分摊"羊毛"。
为了使分摊尽可能的公平，两人希望各自拿到的物品价值总和尽可能的平均。
形式化的：给定 $$$n+1$$$ 个物品，价值分别为 $$$x,a_1,a_2,\cdots,a_n$$$。
设 $$$U = {x,a_1,a_2,\cdots,a_n}$$$，将 $$$U$$$ 划分为两个集合 $$$A$$$ 和 $$$B$$$，满足：
- $$$A \cup B = U$$$
- $$$A \cap B = \emptyset$$$
- $$$x \in A$$$
请你最小化 $$$|\sum_{x\in A}x - \sum_{x\in B} x|$$$，输出这个值。
第一行输入两个正整数 $$$n$$$，$$$x$$$（$$$1\le n\le 10^2$$$, $$$1\le x\le 10^2$$$），分别表示物品数量、荷包价值。
接下来一行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i \le 10^2$$$），表示每个物品的价值。
输出一个整数，表示答案。
3 24 2 3
1
麦田无边无际，阳光照在麦田上、麦穗连在一起，仿佛金色的湖。
她的家人牵着她的手，跑在这风浪中。她笑着跌倒在金色的海洋里，开心地笑着。
良有 $$$n$$$ 条不连贯的与满穗有关的信息，无法将其联系起来。
问过满穗过后，满穗给出了 $$$m$$$ 对信息之间的关系，每一对关系在良眼里都有一个可信度。
良希望用尽可能少的关系把这些信息联系起来，并且整件事情的可信度尽可能的大。
形式化的：给定 $$$n$$$ 个点，$$$m$$$ 条边，每条边有边权。
选择最少数量的边使整个图联通，并且使得边权和最大。
如果无法使得图联通，输出 -1。
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n \le 10^5$$$，$$$1\le m \le 10^6$$$），分别表示信息和信息关系的数量。
接下来 $$$m$$$ 行，每行输入三个正整数 $$$u_i$$$，$$$v_i$$$，$$$w_i$$$（$$$1\le u_i,v_i\le n$$$，$$$1\le w_i \le 10^9$$$），分别表示 $$$u_i$$$ 和 $$$v_i$$$ 信息之间可以连贯，可信度 $$$w_i$$$。
输出一个整数，表示答案。
4 51 2 23 1 32 1 43 4 12 4 6
13
过了这么多年，我本以为自己改变了、变强了、从羊变成了狼，不用再畏惧任何事。
然而，我还是无法摆脱那一年的噩梦。
白袍——乌甲素包巾！丈八蛇矛——手内握哎 。
影子戏里，是刘关张三人大战赤兔吕布的场景。
白幕可以抽象成一个 $$$n\times m$$$ 的网格，满穗希望在上面放若干个骑兵。
满穗希望它们互不攻击。
请你帮忙计算网格中最多能放多少个互不攻击的骑兵。
形式化的：给定一张 $$$n\times m$$$ 的网格。
计算这张网格内最多能放多少个互不攻击的骑兵。
对于位于 $$$(i, j)$$$ 的骑兵，可以攻击到的位置为 $$$(i-2, j+1)$$$，$$$(i-1, j+2)$$$，$$$(i+1, j+2)$$$，$$$(i+2, j+1)$$$，$$$(i+2, j-1)$$$，$$$(i+1, j-2)$$$，$$$(i-1, j-2)$$$，$$$(i-2, j-1)$$$，输入下图所示：
有多组测试数据。第一行输入一个正整数 $$$T$$$（$$$1\le T \le 10^5$$$），表示测试数据组数。
每组测试数据输入一行，其中有两个正整数 $$$n$$$，$$$m$$$（$$$1\le n, m\le 10^9$$$），表示网格大小。
每组测试数据输出一行，包含一个整数，表示答案。
22 45 4
410
那么，我该相信谁。
该怎么选？
良的善恶在挣扎。
良的原则可以抽象为有 $$$n$$$ 个部分，每一部分权重为 $$$a_i$$$。
良的善念与这个长度为 $$$n$$$ 的序列所有的上升子序列的和有关。
现在请你计算这个值。
形式化的：给定一个长度为 $$$n$$$ 的序列 $$$a_1, a_2, \cdots, a_n$$$，现在请你计算下列计算式的值。 $$$$$$ W = \sum_{S\subseteq N}\sum_{i=1}^{|S|}a_{S_i} $$$$$$ 其中 $$$N$$$ 为 $$$\{1,2,\cdots,n\}$$$，$$$S$$$ 为 $$$N$$$ 的子集，且满足 $$$\forall i \in [2, |S|]$$$ 都有 $$$a_{S_{i - 1}} \lt a_{S_i}$$$。
现在你需要计算 $$$W$$$ 的值，由于答案可能非常大，请输出对 $$$998244353$$$ 取模后的答案。
第一行输入一个正整数 $$$n$$$（$$$1\le n \le 5\times 10^5$$$），表示序列长度。
第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i\le 10^9$$$），描述了序列。
输出一个整数，表示答案。
35 2 3
15
很久以前，在那一场大爆炸发生之前，在良爷小的时候……
你想成为什么样的人呢？
良深知这世道，不是"侠"能活的世道。
成为"侠"的梦想早已破灭，也就无法再挥剑向不公，仗剑走天涯。
但另一个难题摆在良的面前。
"我该送她去复仇吗？"
"还是劝她不要再去复仇？"
早已被唤醒的良知影响着良，良不希望自己亲手送满穗去复仇。
两种选择分别对应着两个序列 $$$A$$$ 和 $$$B$$$。
良可以操作若干次，每次将 $$$A$$$ 中的一个值加上或减去 $$$A$$$ 与 $$$B$$$ 中位置不同的一对差值。
为了尽可能的劝说满穗放弃复仇，良需要最小化两序列差的绝对值之和。
形式化的：给定两个长度为 $$$n$$$ 的序列 $$$A$$$ 和 $$$B$$$，设 $$$A$$$ 与 $$$B$$$ 的权值为 $$$W$$$。 $$$$$$ W = \sum_{i=1}^n |a_i-b_i| $$$$$$ 你可以执行以下操作任意次（可能是 $$$0$$$）：
- 选择两个下标 $$$i$$$, $$$j$$$，令 $$$a_i := a_i+|a_j - b_j|$$$ 或 $$$a_i:=a_i-|a_j-b_j|$$$，其中 $$$i \ne j$$$。
计算任意次操作后，$$$W$$$ 的最小值。
第一行输入一个正整数 $$$n$$$（$$$1\le n\le 10^5$$$），表示序列长度。
第二行输入 $$$n$$$ 个整数 $$$a_1,a_2,\cdots,a_n$$$（$$$|a_i|\le 10^9$$$），表示序列 $$$A$$$。
第三行输入 $$$n$$$ 个整数 $$$b_1,b_2,\cdots,b_n$$$（$$$|b_i|\le 10^9$$$），表示序列 $$$B$$$。
输出一个整数，表示答案。
32 6 42 4 1
1
很多事，对于一个人的一生来说，是头一回，也大概是最后一回。
这大概是我与小羊们在他人面前演的第一次戏，也是最后一次。
两人打的难舍难分。
良最初体力值和攻击力为 $$$a$$$，闯将的体力值和攻击力为 $$$b$$$。
战斗分为若干个回合，每个回合双方都同时进攻对方，使对方的生命值减去自身攻击力的值，且自身攻击力减少 $$$1$$$。
若有一方的体力值先降低至 $$$0$$$ 及以下，则另一方获胜。
如果双方在同一回合的体力值均降低至 $$$0$$$ 及以下，则为平局。
若良获胜输出 Liang，闯将获胜输出 Chuang，平局则输出 Pingju。
第一行输入两个正整数 $$$a$$$, $$$b$$$（$$$1\le a,b \le 10^9$$$），分别表示良和闯将的体力值及攻击力。
输出一行，表示获胜方或平局。
21 10
Liang
你还是你。
你不是狼，是"良"。
清晨，良来到集市，准备为马上要分别的小羊们买些好吃的好玩的，好好道个别。
集市有 $$$n$$$ 个商铺，自西向东依次排开，编号为 $$$1,2,3,\cdots,n$$$，其中 $$$1$$$ 号商铺在最西边， $$$n$$$ 号商铺在最东边。
良最开始在编号为 $$$1$$$ 的商铺位置，一直向东走，他每次移动会随机均匀的走到在当前位置东边的一家商铺并逛 $$$1$$$ 次该店铺（包括当前所在位置商铺）。
注：在最开始时良并不会逛 $$$1$$$ 号商铺。
由于并不需要买特别多东西，因此他最多会逛 $$$k$$$ 次商铺。
良想知道，逛完 $$$k$$$ 次商铺的时候他的所在位置的概率。
形式化的：有 $$$n$$$ 个节点，以此编号为 $$$1,2,3,\cdots,n$$$，初始时在 $$$1$$$ 节点。
你必须执行以下操作 $$$k$$$ 次：
- 设当前节点为 $$$x$$$，你会等概率的选择 $$$[x, n]$$$ 之间的一个节点，并移动到该节点上。
随后 $$$q$$$ 次询问，每次询问一个位置 $$$x$$$，你需要回答在 $$$k$$$ 次操作后当前位置恰好在 $$$x$$$ 节点上的概率。
第一行输入三个正整数 $$$n$$$，$$$k$$$，$$$q$$$（$$$1\le n,k\le 2\times10^6$$$，$$$1\le q\le 10^5$$$），分别表示商铺个数，逛商铺次数，询问次数。
接下来 $$$q$$$ 行，每行输入一个正整数 $$$x$$$（$$$1\le x\le n$$$），表示询问位置。
输出 $$$q$$$ 行，每行输出一个小数，表示第 $$$i$$$ 次查询的答案。
当你的答案与标准答案的绝对误差或相对误差不超过 $$$10^{-6}$$$ 时将被视为正确。具体而言，设你的答案为 $$$a$$$，裁判答案为 $$$b$$$，当且仅当满足 $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-6}$$$ 时，你的答案才会被判为正确。
4 2 224
0.14583333 0.52083333
若是这样的话……
你觉得自己还该复仇吗？
良需要在宵禁之前找到满穗。
鼓楼附近有一些满穗可能藏匿的地点，良知道这些地点的路径，他希望尽快的找遍这些地点。
形式化的：给定一张具有 $$$n$$$ 个点，$$$m$$$ 条边的无向图，起点为 $$$s$$$。
通过一条边所花费的时间为 $$$w_i$$$。
请你计算从 $$$s$$$ 出发走过所有点花费的最小时间是多少。
第一行输入三个整数 $$$n$$$，$$$m$$$，$$$s$$$（$$$1\le n\le 20$$$，$$$n-1\le m \le \frac{n(n-1)}{2}$$$，$$$1\le s\le n$$$），分别表示地点数量，路径数量和良当前所在的起点。
接下来 $$$m$$$ 行，每行输入三个正整数 $$$u_i$$$，$$$v_i$$$，$$$w_i$$$（$$$1\le u_i,v_i\le n$$$，$$$1\le w_i\le 10^9$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 且边权为 $$$w_i$$$ 的边。
保证给定的图为连通图，且不存在重边和自环。
输出一个正整数，表示答案。
4 5 31 2 22 3 13 4 41 4 22 4 5
5
这种突如其来的"不见"，以及那永远没有答案的结果，便是她对我的报复。
最温柔却最残忍的报复。
即便如此，良依然希望找到满穗。
洛阳城附近有若干条河流，其中一些相互联通。
每个河流有各自的宽度，宽度大小与能否找到满穗有关。
1. 对于一个环流，其宽度由其组成的最大河流宽度决定。
2. 对于一个链流，其宽度由其组成的最小河流宽度决定。
良需要你帮他找到决定所有河流宽度的河流，并输出方案，那里很可能找到满穗。
形式化的：给定一张 $$$n$$$ 个点的无向图，每个点有一个权值 $$$a_i$$$。
你可以执行若干次操作，最终使得整张图缩成一个点，每次操作选择以下两种操作的其中一种：
1. 选择一个简单环$$$^{\text{∗}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最大权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。
2. 选择一条链$$$^{\text{†}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最小权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。
其中，第 $$$i$$$ 次操作建立的新节点编号为 $$$n + i$$$。
请你找到在图缩成一个点后，能保留的最大权值，并输出一种操作方案，且操作次数不超过 $$$n$$$ 次。
如果存在多种合法方案，输出任意一种。
本题为 $$$\text{M}$$$ 题的 $$$\text{std}$$$ 程序。
$$$^{\text{∗}}$$$一条至少包含三条边的闭合路径，其中除了起点和终点相同外，其余所有顶点均不重复，且所有边也不重复。
$$$^{\text{†}}$$$一条所有顶点都不重复的路径。
有多组测试数据。
第一行输入一个正整数 $$$T$$$（$$$1\le T \le 10^3$$$），表示测试数据组数，对于每组测试数据：
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n \le 10^5$$$，$$$n - 1 \le m \le \min\left(\frac{n(n-1)}2,10^6\right)$$$），分别表示点数量，边数量。
第二行输出 $$$n$$$ 个整数 $$$a_1, a_2,\cdots a_n$$$（$$$1\le a_i \le n$$$），表示点权。
保证点权之间互不相同。
接下来 $$$m$$$ 行，每行输入两个正整数 $$$u_i$$$，$$$v_i$$$（$$$1\le u_i,v_i\le n$$$，$$$u_i \ne v_i$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。
保证给定的图为连通图，且不存在重边、自环。
保证所有数据 $$$n$$$ 之和不超过 $$$10^5$$$，$$$m$$$ 之和不超过 $$$10^6$$$。
对于每组测试数据：
第一行输出一个正整数，表示保留的最大权值。
第二行输出一个整数，表示操作次数 $$$k$$$。
接下来 $$$k$$$ 行，每行输出若干个数字。
第 $$$i$$$ 行第一个整数表示操作方式，第二个该次操作选择的节点数量 $$$l$$$。
接下来 $$$l$$$ 个数字，表示该次操作选择的节点序列 $$$p_1, p_2, \cdots,p_l$$$，其中任意 $$$i\ne j$$$ 均满足 $$$p_i \ne p_j$$$。
对于正整数 $$$i$$$（$$$1\le i \lt l$$$），在 $$$p_i$$$ 与 $$$p_{i+1}$$$ 均存在一条边。
若为操作 $$$1$$$，额外要求 $$$p_1$$$ 与 $$$p_l$$$ 之间存在一条边。
24 44 2 1 31 22 31 31 44 41 2 4 31 22 31 31 4
3 2 1 3 1 2 3 2 2 4 5 4 2 2 2 1 4 1 3 2 3 5
杀，我会去杀、用我这条命去换我们仇人的命！
杀！用我的命去证明这世道是错的—天，亦是错的！
湖边寻到满穗后，良有太多疑问。
良的问题和满穗的实情可以抽象成两个 $$$n\times m$$$ 的 $$$01$$$ 矩阵 $$$A$$$ 和 $$$B$$$。
矩阵每一个位置 $$$(i, j)$$$ 有一个权值，如果该点为 $$$1$$$，权值为 $$$0$$$，否则为与它相邻的 $$$1$$$ 的数量（两个格子相邻当且仅当它们共用一个点或一条边）。
良的每次提问可以表示为反转 $$$A$$$ 中的某一位。
为了清楚事实，良希望尽可能的少提问，使得 $$$A$$$ 和 $$$B$$$ 的权值和相等。
形式化的：给定两个 $$$n\times m$$$ 的 $$$01$$$ 矩阵 $$$A$$$ 和 $$$B$$$。
矩阵 $$$(i, j)$$$ 位置的值为 $$$1$$$ ，权值为 $$$0$$$，否则为与它相邻的 $$$1$$$ 的数量（两个格子相邻当且仅当它们共用一个点或一条边）。
你可以执行以下操作：
选择 $$$A$$$ 的一个位置 $$$(i, j)$$$，反转这一位的 $$$01$$$ 值。
构造一种操作序列，在操作后两矩阵的权值和相等，且操作序列长度不能超过 $$$\lfloor \frac{nm}2 \rfloor$$$。
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n\times m \le 10^6$$$），表示矩阵大小。
接下来 $$$n$$$ 行，第 $$$i$$$ 行输入一个长度为 $$$m$$$ 的 $$$01$$$ 字符串，表示 $$$A_i$$$。
接下来 $$$n$$$ 行，第 $$$j$$$ 行输入一个长度为 $$$m$$$ 的 $$$01$$$ 字符串，表示 $$$B_j$$$。
第一行输出一个整数 $$$k$$$（$$$0\le k \le \lfloor \frac{nm}2 \rfloor$$$），表示操作序列的长度。
接下来 $$$k$$$ 行，每行输出两个正整数 $$$i$$$ 和 $$$j$$$，表示对 $$$A$$$ 的操作位置。
2 3011000101111
1 2 3
迎接我们的，是连绵不断的晴天，一望无际的麦田。
以及一个人人吃饱饭，不再有饿殍的时代……
就像计划的那样，良和穗跑不掉了。
但哪怕如此，良也依然想尝试一番。
门前有 $$$n$$$ 个捕快，每个捕快有各自的战力值 $$$a_i$$$，良的体力值为 $$$k$$$。
由于捕快的数量太多，全部肃清是不可能的。
但捕快的防线存在缺陷，如果存在一对 $$$(i, j)$$$ 且 $$$i \ne j$$$，使得 $$$a_i \oplus a_j \le k$$$，其中 $$$\oplus$$$ 为异或运算，那么良穗可以趁机闯出捕快的包围。
请你帮良判断他们有可能冲出重围吗。
形式化的：给定一个长度为 $$$n$$$ 的序列 $$$a_1, a_2, \cdots,a_n$$$ 和一个正整数 $$$k$$$。
查询是否存在一对 $$$(i, j)$$$ 且 $$$i\ne j$$$，使得 $$$a_i\oplus a_j \le k$$$，其中 $$$\oplus$$$ 为异或运算。
请注意本题特殊的空间限制。
第一行输入两个正整数 $$$n$$$，$$$k$$$（$$$2\le n \le 10^6$$$, $$$1\le k \lt 2^{30}$$$），分别表示捕快数量和良的体力值。
第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i \lt 2^{30}$$$），表示捕快各自的战力值。
输出 Yes 或 No，表示良穗能否杀出重围。
3 44 6 3
Yes
开城门，迎闯王，闯王来了不纳粮！
迎闯王、不纳粮！迎闯王、不纳粮！
攻破洛阳城后，李自成派人找了一口大锅，把豚妖和它养的几只梅花鹿一起扔进锅里。
为了让百姓和士兵狠狠出一口几年以来积压的恶气，李自成打算把锅放在百姓和将士们的正中央，以便所有人目睹当报应降临到这横征暴敛，压榨百姓的罪魁祸首身上时，其求饶和痛苦的神情。
形式化的：所有人的位置可以抽象成一个二维坐标系，给定 $$$n$$$ 个士兵及百姓的位置 $$$(x_i, y_i)$$$。
锅的坐标为 $$$(a,b)$$$，这个点将坐标系划分为四个部分：
- $$$\left\{(x,y)~|~a\le x,b\le y\right\}$$$
- $$$\left\{(x,y)~|~a\le x,y \lt b\right\}$$$
- $$$\left\{(x,y)~|~x \lt a,b\le y\right\}$$$
- $$$\left\{(x,y)~|~x \lt a,y \lt b\right\}$$$
现在李自成希望选择锅的坐标，使得四部分点的数量尽可能的平均，即最大化四部分点集大小的最小值的坐标。
第一行输入一个正整数 $$$n$$$（$$$1\le n\le 10^5$$$），表示士兵及百姓的数量。
接下来 $$$n$$$ 行，每行包含两个整数 $$$x$$$，$$$y$$$（$$$|x|,|y|\le 10^9$$$），表示士兵及百姓的坐标。
输出包含两个整数 $$$a$$$，$$$b$$$（$$$|a|,|b|\le 10^9$$$），表示锅的坐标。
如果有多个合法的点，输出任意一个。
41 11 -1-1 1-1 -1
0 0
我能和她一起，看着她活着。
仅仅如此，对我而言便是最好的事了。
自此烟雨落金城，一人撑伞两人行。
九年之约，良穗相遇。
良已践行与满穗立下的湖畔之约，满穗再次宽限良，允许他实现最后的愿望。
就此，两人乘着小船，踏上了扬州之旅。
包括洛阳和扬州在内的若干个城镇由多条河流相连，且每个城镇有各自的发展水平值，船夫需要提前规划路线。
在船夫的规划有两种方式：
- 选择若干个城镇，且这些城镇能组成一个简单环，保留被选择的城镇中发展程度值最大的城镇，其中原本未被选择城镇连接到被选择城镇的河流视为连接到最后保留的城镇。
- 选择若干个城镇，且这些城镇能组成一个链，保留被选择的城镇中发展程度最小的城镇，其中原本未被选择城镇连接到被选择城镇的河流视为连接到最后保留的城镇。
现在给定船夫的操作方案，请你帮忙计算最后保留城镇的发展程度值，若操作不合法或操作后不为一个点，输出 -1。
形式化的：给定一张有 $$$n$$$ 个点的无向图，每个节点有一个权值 $$$a_i$$$。
给定一个操作序列，其中包含两种合法操作：
- 选择一个点序列 $$$P$$$，其中任意两点不相同，且对于 $$$1\le i\le|P|$$$，均满足 $$$p_i$$$ 与 $$$p_{\left(i~\text{mod}~|P|\right)+1}$$$ 之间存在一条边，即这些点构成简单环$$$^{\text{∗}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最大权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。
- 选择一个点序列 $$$P$$$，其中任意两点不相同，且对于 $$$1\le i \lt |P|$$$，均满足 $$$p_i$$$ 与 $$$p_{i+1}$$$ 之间存在一条边，即这些点构成一条链$$$^{\text{†}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最小权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。
其中，第 $$$i$$$ 次操作建立的新节点编号为 $$$n + i$$$。
请你计算操作后，在图缩成一个点后所保留的权值，若操作不合法或图不仅剩一点，输出 -1。
本题为 $$$\text{I}$$$ 题的 $$$\text{checker}$$$ 程序。
$$$^{\text{∗}}$$$一条至少包含三条边的闭合路径，其中除了起点和终点相同外，其余所有顶点均不重复，且所有边也不重复。
$$$^{\text{†}}$$$一条所有顶点都不重复的路径。
有多组测试数据。
第一行输入一个正整数 $$$T$$$（$$$1\le T \le 10^3$$$），表示测试数据组数，对于每组测试数据：
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n \le 10^5$$$，$$$n-1\le m\le \min\left(\frac{n(n-1)}{2},10^6\right)$$$），分别表示图中点数量，边数量。
接下来一行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i\le n$$$），表示第 $$$i$$$ 个点的点权。
保证点权之间互不相同。
接下来 $$$m$$$ 行，每行输入两个正整数 $$$u_i$$$，$$$v_i$$$（$$$1\le u_i,v_i\le n$$$，$$$u_i \ne v_i$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。
保证给定的图为连通图，且不存在重边、自环。
接下来一行输入一个正整数 $$$q$$$（$$$1\le q\le n$$$），表示操作序列长度。
接下来 $$$q$$$ 行，第 $$$i$$$ 行输入若干个整数 $$$op$$$，$$$l$$$，$$$p_1,p_2,\cdots,p_l$$$（$$$1\le op\le2$$$，$$$1 \lt l\le n$$$，$$$1\le p_i\le 2\times n$$$），描述了操作方式和操作所选的点序列。
保证所有数据 $$$n$$$ 之和不超过 $$$10^5$$$，$$$m$$$ 之和不超过 $$$10^6$$$。
对于每组测试数据：输出一行，包含一个整数，表示答案。
24 41 2 4 31 22 31 31 421 3 1 2 32 2 5 44 44 2 1 31 22 31 31 411 3 2 1 4
3-1