牛客系列赛命题规范——V2.0.beta（公示）

为了提高参赛选手体验，我们草拟了若干条出题相关规范。希望征求算法竞赛选手的意见，评估每个条例的严肃等级。或者补充一些我们暂未想到的条例。

您可以访问 我们的官方问卷 填写您的意见。

我们会定期更新问卷以及本帖内容公示当前的规范，点此前往 V1.0 。

全文规范

以下为根据问卷整理的相关规范，分为四个等级。特别地，我们有权根据守则对您的题目进行一定的调整或限制。

强制遵守

该等级内容前使用红色圆形标注，且字体加粗。您在命题的过程中必须遵守，否则不允许题目用于公开比赛。

严格遵守

该等级内容前使用橙色圆形标注。您在命题的过程中应当尽可能的遵守，除非与题目解题方式等产生较大影响。

建议遵守

该等级内容前使用绿色圆形标注。在您的习惯范围内可以选择性遵守、参考使用，这部分条例为某些出题人的习惯或收集到来自选手认为影响做题体验的反馈。

题面规范

类目	编号	规则描述
命题思路	A01	出题前，请务必先查看《牛客系列赛初审标准》和《牛客系列赛流程与说明》。
	A02	出题前，我们推荐您阅读 OI-Wiki：出题。
	A03	确保题目的原创性。如有必要，请使用原题机进行基础思路的检查，避免撞题问题。对于简单问题（周赛前四题、小白月赛前四题、练习赛前两题），我们允许您在一定程度上的相似，但是禁止出现直接复制网络代码可以通过、或只需要做微小修正（改数组大小、改输入输出）的题目。对于复杂问题，尽可能的规避相似，禁止出现核心实现思路相同（套了个壳、套了个简单转化）的题目。对于数学推导类、公式类题目，如有必要，您还可以使用 OEIS：整数数列线上大全进行检查，避免一个公式直接出的问题。
	A04	尽可能的提高题目的质量。我们不建议您以"以前做某题时读错了"为由，命制与原题相似的题目、或在其基础上进行加强。我们不建议您在日常系列赛中命制大模拟、大模板题，需要考虑到无模板选手从头开始书写代码所需的时间。
题面文本格式	A05	禁止直接在题面出现与题目完全无关的背景描述。如果你需要书写这部分内容，请使用 `blockquote` 标签（引用），而不要直接写入题面。
	A06	禁止在题目中使用明显的语言倾向。若仅描述某种算法的实现，禁止出现特定语言实现的代码，应使用伪代码代替。
	A07	如与解题的核心算法考点/题目难度无关，当出现多解时，尽可能编写 Special Judge 。不得以怕麻烦为理由要求选手输出特解，除非题目本身考察的内容就为该特解，或求解特解的过程为题目难度设计的一部分。参考格式如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
	A08	题面中所出现的全部变量与常量都应当使用 $\LaTeX$ 公式描述，您可以参考 KaTeX官方文档获取完整的格式语法。目前，对于系列赛，在内测阶段会有协调员帮助您进行格式统一，您不必过多拘泥于题目的公式准确度。
	A09	除集合、图表等数学惯用符号外，题目中所出现的变量都应当使用小写字母。避免多字母变量；如果一定需要，多字母变量应当渲染为罗马体，而不是斜体（例如 $\mathrm{dis}_{i, j}$ ，如果您使用 $\LaTeX$ ，请使用 `\mathrm{···}` 、`\textrm{···}` 或 `{\rm ···}` 标签）。
	A10	对于区分 easy version 和 hard version 的题目，应在醒目位置（一般是题目开头位置）注明与另一个版本的差异。
	A11	题目中所出现的所有角色名称都应该是广泛使用的通用名称，不要使用昵称、用户名。
	A12	使用大括号 `\{···\}` 表示序列、数组、集合等，尽可能仅将方括号用于描述区间。
	A13	表示序列、数组、集合时，应当先描述元素数量，随后列出第一、第二和最后一个元素，中间使用省略号 `\dots` 间隔。元素的表示应该同时包含名称与下标。参考格式对于给定的由 $n$ 个整数组成的数组 $\{a_1,a_2,\dots,a_n\}$ 和由 $m$ 个整数组成的排列 $\{b_1,b_2,\dots,b_m\}$ 。 `对于给定的由 $n$ 个整数组成的数组 $\{a_1,a_2,\dots,a_n\}$ 和由 $m$ 个整数组成的排列 $\{b_1,b_2,\dots,b_m\}$ 。`
数学定义	A14	当出现不常见的数学定义时，必须在题目中明确指出。除非您的比赛面向的选手层次较高，则可以选择性的加以省略，否则，应当是越详细越好。
	A15	要求选手输出取模/取余的答案时，若原本的答案存在负数，则慎重考虑使用"取模"还是"取余"。必须给出原本答案是负数的例子或在题目描述中进行强调。细则不同语言对于负数"取余"有着完全不同的实现和处理方式，但"取模"有着明确的数学定义，例如 $(-1)\bmod 5 = 4$ ，但对于"取余"，在没有特别声明的情况下， $-1$ 和 $4$ 均是正确的答案，您应当做出详细的解释说明。
	A16	要求选手准确输出时，若答案需要进行除法运算，则慎重考虑使用"以分数形式输出"或是"以除法取余的形式输出"。参考格式可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出 $p$ 和 $q$ 。 `可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \cdot q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998\,244\,353$ ，$q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。` 可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \cdot q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998\,244\,353$ ， $q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。 `可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \cdot q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998\,244\,353$ ，$q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。`
	A17	你需要区分常用语"子串/子数组/子序列"等相近的概念，不建议出现"字段/子区间"等相似词。为了便于理解，建议使用"连续"一词修饰。
	A18	当题目涉及到子串/子区间/子序列/前缀/后缀等概念时，必须显式的注明：①是否包含自身；②是否可以为空。或在样例中有所体现。参考格式子序列为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。子序列为从原数组中删除任意个（可以为零、可以为全部）元素得到的新数组。子数组为从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组
	A19	当题目描述中涉及到"集合"的概念时，需注意是否为"可重集"。当涉及到"子集"概念时，需注意是否为"真子集"，且是否包含"空集"。
	A20	当涉及到有多少种不同的XX满足条件的描述时，需对"不同"做相应的解释。若题目首先需要选手进行某些"操作"，再求不同的"值"时，使用"本质不同"强调其值上的差别而非操作上的差异。例如：求本质不同的子序列/子串个数。
高级定义	A21	在题目中提供数据生成器、强制在线的加解密算法必须真实有效、具有可移植性，不得有误导或者任何欺骗行为。您应当在得到协调员确认的前提下使用。细则不得出现例如，某道题目在描述中要求选手强制在线，但强制在线的加密算法存在漏洞可以绕过改为离线算法；某道题目声称自己提供随机数生成器，但该生成器存在数据分布不均的特性或者存在循环节，且标程使用了该特性。你需要极为慎重的使用随机数生成器，确保在你熟练了解的情况下使用。例如，由于不同编译器不保证 `std::random` 或者 `mt19937` 等随机数算法使用完全相同的随机数表，使用此方法会导致数据在不同平台不一致。
	A22	若在题目中提供数据生成器、强制在线的加解密算法，必须在样例解释/备注中进行整个加密过程的详细讲解（加密前的数据、加密过程、加密后的数据）。
	A23	要求输出 $n$ 个答案的异或和等场景时，必须在样例解释中提供部分有意义的信息。

输入规范

类目	编号	规则描述
数据量	B01	输入输出总字符量应当小于 $10^7$ ，通常情况下禁止超过 $2 \times 10^7$ 。如果输入的数据量需要超过 $2 \times 10^7$ ，你应当先与协调员沟通，当协调员同意后，方可使用在题目中给出（随机）数据生成器伪代码，或混合多种输入的方式。如果输出的数据量需要超过 $2 \times 10^7$ ，你应当先与协调员沟通，当协调员同意后，方可使用输出异或和、或者求和取余的方式。细则你应当计算单个字符的数量。例如，当值域为 $[1, 10^{18}]$ 时，数字的个数不应超过 $5 \times 10^5$ ，因为 $18 \times 5 \times 10^5 = 9 \times 10^6$ ，已经接近极限。特别地，对于实数，其读入会更慢一些。读入的实数个数不应当超过 $2 \times 10^5$ 。
数据量	B02	如果输入的总字符量超过 $5 \times 10^6$ ，应当在题目描述醒目位置提醒建议选手使用快速的输入方式。
输入文本格式	B03	输入描述应该仅包含输入格式和数据范围，禁止仅在此处填写解题的关键条件。
	B04	应当从常见的 ICPC 赛制输入规范与 IOI 赛制输入规范中选择一种，并严格遵守。我们更推荐您使用 ICPC 赛制输入规范。 ICPC 赛制：应当先说明变量的输入格式，随后列出全部变量，再给出每一个变量的上下限约束，最后给出变量的含义。约束应当紧跟变量在同一行给出；约束应在括号中，应同时包含上下限；变量的含义需要按照题干中的阐释动态的调整。参考格式（该部分完整举例请参考文末）第一行输入两个整数 $r,c\ (1 \leq r, c \leq 10^6;\ 1 \leq r \times c \leq 10^{6})$ 代表矩阵的行数和列数。此后 $r$ 行, 第 $i$ 行输入一个长度为 $c$ ，仅由 $\texttt{$ 和 $\texttt{$ 两个字符构成的字符串 $s$ 用于描述矩阵的第 $r$ 行。 `第一行输入两个整数 $r,c\ (1 \leq r, c \leq 10^6;\ 1 \leq r \times c \leq 10^{6})$ 代表矩阵的行数和列数。此后 $r$ 行, 第 $i$ 行输入一个长度为 $c$ ，仅由 $\texttt{"0"}$ 和 $\texttt{"1"}$ 两个字符构成的字符串 $s$ 用于描述矩阵的第 $r$ 行。` IOI 赛制：与 ICPC 赛制类似，但变量的上下限约束在《备注》一栏中给出。参考格式对于前 $10\%$ 的测试数据，保证 $1\leq a,b\leq 10$ 。对于前 $30\%$ 的测试数据，保证 $1\leq a,b\leq 10^{9}$ 。对于不包括在前 $30\%$ 的另外 $10\%$ 的数据，保证 $a=0$ 。对于 $100\%$ 的测试数据，保证 $-10^{9}\leq a,b \leq 10^{9}$ 。 `对于前 $10\%$ 的测试数据，保证 $1\leq a,b\leq 10$ 。对于前 $30\%$ 的测试数据，保证 $1\leq a,b\leq 10^{9}$ 。对于不包括在前 $30\%$ 的另外 $10\%$ 的数据，保证 $a=0$ 。对于 $100\%$ 的测试数据，保证 $-10^{9}\leq a,b \leq 10^{9}$ 。`
	B05	应当尽可能地使文本的结构反映输入的结构。使用不同段落描述在不同行给出的输入、使用同一段落描述在同一行给出的输入。如果是单行输入，应当注明当前所在的行数。参考格式（该部分完整举例请参考文末）第一行输入一个整数 $n\ (1 \leq n \leq 10^5)$ 代表数组中的元素数量。第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (0\leq a_i \leq 2 \times 10^6)$ 代表数组元素。 `第一行输入一个整数 $n\ (1 \leq n \leq 10^5)$ 代表数组中的元素数量。第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (0\leq a_i \leq 2 \times 10^6)$ 代表数组元素。` 如果是多行相同格式的输入，注明相同格式的行数。参考格式（该部分完整举例请参考文末）第一行输入一个整数 $n\ (1 \leq n \leq 10^5)$ 代表数组中的元素数量。此后 $n$ 行，第 $i$ 行输入一个整数 $a_i\ (0\leq a_i \leq 2 \times 10^6)$ 代表数组中的第 $i$ 个元素。 `第一行输入一个整数 $n\ (1 \leq n \leq 10^5)$ 代表数组中的元素数量。此后 $n$ 行，第 $i$ 行输入一个整数 $a_i\ (0\leq a_i \leq 2 \times 10^6)$ 代表数组中的第 $i$ 个元素。`
	B06	一旦题干中的任何数字超过了三位（ $1000$ ），都需要使用科学计数法表示，以避免可能的误解。如果科学计数法描述复杂，以千分位空格或千分符替代。参考格式在一行上输入两个整数 $n, p \left(1 \leq n \leq 10^5;\ 1 \leq p \leq 10^9 + 7 \right)$ 代表给定的数字与幂。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。由于答案可能很大，请将答案对 $11'451'419$ 取模后输出。 `在一行上输入两个整数 $n, p \left(1 \leq n \leq 10^5;\ 1 \leq p \leq 10^9 + 7 \right)$ 代表给定的数字与幂。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。由于答案可能很大，请将答案对 $11'451'419$ 取模后输出。`
	B07	多测题目，使用当前主流的明确多测组数的方式，在第一行输入组数，随后分段描述每一组的情况（类似于一个递归的样式）。禁止要求选手读取数据直到文件结尾 `EOF` 。参考格式每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^5\right)$ 代表数据组数，每组测试数据描述如下：除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$ 。 `每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^5\right)$ 代表数据组数，每组测试数据描述如下：除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$ 。`
	B08	默认使用单个空格进行数据的间隔，应当假设选手知晓这一点，直接省略以精简描述的语言。如果你的间隔符号不为单个空格（我们十分不建议，但如果确实需要），必须在醒目处重点说明。参考格式在一行上输入若干个字符串，每个字符串长度为 $1 \leqq {\rm length}(s) \leqq 20$ ，仅由大小写字母构成，代表一个单词。单词间还夹杂了一定数量的非字母字符（但保证是可见字符），代表分隔符。 `在一行上输入若干个字符串，每个字符串长度为 $1 \leqq {\rm length}(s) \leqq 20$ ，仅由大小写字母构成，代表一个单词。单词间还夹杂了一定数量的非字母字符（但保证是可见字符），代表分隔符。`
输入实数	B09	如与题目解题方式/题目难度无关，计算几何题目中输入点坐标时，使用整数而非浮点数。浮点数通常会导致较慢的读入速度（ `013` ）和预期外的精度问题。如果您一定要输入浮点数，建议您首先测试常见的浮点数类型、常见的读入方式，确保可控。浮点数可能会导致预期外的近似无解问题，例如近似共线、-0.0 等等。如果您一定要输入浮点数，建议您广泛的测试这些可能出现的边界情况。请参考 `58` 。
输入实数	B10	如果您需要输入浮点数，应当明确输入的位数。参考格式输入一个小数点后位数不超过两位的实数。
输入字符串	B11	字符串问题必须显式的说明所包含的字符集，特别是特殊字符（非大小写字母、非数字）。
	B12	字符的输入只能包含可见的 `ASCII` 字符（包括空格），禁止出现中文和 `Unicode` 字符。以免编程语言、选手终端出现不支持的情况，可见字符集参考。
	B13	字符串问题应当先给出字符串的长度，随后输入字符串。参考格式在第一行输入一个整数 $n \left(1 \leq n \leq 10^6 \right)$ 代表字符串长度。第二行输入一个长度为 $n$ ，由大小写字母和空白字符构成的字符串 $s$ 。第三行输入一个长度为 $n$ ，由可见 $\sf{Ascii}$ 字符构成的字符串 $t$ 。 `在第一行输入一个整数 $n \left(1 \leq n \leq 10^6 \right)$ 代表字符串长度。在第二行输入一个长度为 $n$ ，由大小写字母和空白字符构成的字符串 $s$ 。在第三行输入一个长度为 $n$ ，由可见 $\sf{ASCII}$ 字符构成的字符串 $t$ 。`
	B14	字符画题目禁止要求输出前导/后置空格。使用可见字符替代空格，或使用外侧边框。参考格式 `...... ../\.. ./..\. ______` `******** * * * /\ * * / \ * ______ ********`
输入图	B15	图论问题必须显式的说明是单向边还是双向边，在输入描述中必须指出测试数据中是否包含自环、是否包含重边、是否连通、是否带权等信息。参考格式（该部分完整举例请参考文末）第一行输入两个整数 $n,m\left(1 \leq n \leq 10^5;\ 0 \leq m \leq \min\left\{ 10^5, \dfrac{(n-1)\times n}{2}\right\} \right)$ 此后 $m$ 行，第 $i$ 行输入三个整数 $u_i,v_i,w_i \left(1 \leq u_i, v_i \leq n;\ u_i \neq v_i;\ 0 \leq w_i \leq 10^9\right)$ 代表图上第 $i$ 条边双向连接节点 $u_i$ 和 $v_i$ ，边权为 $w_i$ 。保证图连通，没有重边。 `第一行输入两个整数 $n,m\left(1 \leq n \leq 10^5;\ 0 \leq m \leq \min\left\{ 10^5, \dfrac{(n-1)\times n}{2}\right\} \right)$ 此后 $m$ 行，第 $i$ 行输入三个整数 $u_i,v_i,w_i \left(1 \leq u_i, v_i \leq n;\ u_i \neq v_i;\ 0 \leq w_i \leq 10^9\right)$ 代表图上第 $i$ 条边双向连接节点 $u_i$ 和 $v_i$ ，边权为 $w_i$ 。保证图连通，没有重边。`
输入图	B16	树上问题如果是有根树，必须显式的指出根节点或输入根节点，不能让选手通过输入的方式自己推导根节点。

输出规范

类目	编号	规则描述
输出文本格式	C01	对于要求选手输出的内容，确保其具有一定的辨识度。不得使用任何容易混淆的内容，例如 `yes` 、`no` 的题目中不能要求选手输出 `Ye5` 、`n0` 等。
	C02	统一忽略行末空格、忽略文件末回车。禁止加以限制，保证无论选手是否输出行末空格，以及文件末的回车都能通过题目。
	C03	禁止使用过长的字符串，尽可能简洁的输出判断，例如 `YES! This problem have a solution!` 。
	C04	尽可能贴近主流的输出方法，例如在博弈论中，先手通常为 Alice，后手通常为 Bob 。
	C05	禁止仅在输出描述中填写解题的关键条件。
	C06	如有必要，应当在输出描述中采用与输入格式一样的方法，使用文本的结构反映输出的结构，使用变量+约束+含义的形式约束输出。参考格式如果没有从顶点 $s$ 到 $t$ 的路径，直接输出 $-1$ 。否则，请参考下方的格式输出。在第一行上输出一个整数代表你所找到的最短路径的长度。在第二行上输出一个整数 $p \left( 2 \leq p \leq n \right)$ 代表你所找到的路径上点的数量。在第三行上输出 $p$ 个不同的整数代表顶点。在第四行上输出 $p-1$ 个不同的整数代表边。编号即输入顺序，从 $1$ 开始计数。如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。如果没有从顶点 $s$ 到 $t$ 的路径，直接输出 $-1$ 。否则，请参考下方的格式输出。在第一行上输出一个整数代表你所找到的最短路径的长度。在第二行上输出一个整数 $p \left( 2 \leq p \leq n \right)$ 代表你所找到的路径上点的数量。在第三行上输出 $p$ 个不同的整数代表顶点。在第四行上输出 $p-1$ 个不同的整数代表边。编号即输入顺序，从 $1$ 开始计数。如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
	C07	除非证明非常关键，否则，我们不建议您提供虚假多输出分支选择，例如，某一题实际上恒有解，但是您依旧提供了一个无解的输出分支。对于解恒存在的题目、或数据保证解存在的题目，您应当在题目中声明这一点。参考格式数据保证本题恒有解。我们可以证明，答案一定存在。
Special Judge	C08	输出为实数的题目应使用 Special Judge 避免计算误差，并且尽可能的确保标程的输出准确。确保使用 `C++ -> long double` 和 `double` 分别进行测试。参考格式：参考格式由于实数的计算存在误差，当误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\tfrac{\|a-b\|}{\max(1,\|b\|)}\leq 10^{-6}$ 时，您的答案将被接受。 `由于实数的计算存在误差，当误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\tfrac{\|a-b\|}{\max(1,\|b\|)}\leq 10^{-6}$ 时，您的答案将被接受。`
	C09	我们仅建议您使用 `testlib.h` 进行 Special Judge 的编写。否则，请尽可能的测试所有可能的非法输入（如数字、可见字符、不可见字符、汉字等等）、格式错误（范围错误、数量错误、输出超限等等）并进行判定。
	C10	对于确定的逻辑判定题（是否 `YES/NO` 判断、方向 `L/R/U/D` 判断等），应使用 Sepcial Judge 忽略大小写，且在输出描述中注明。参考格式您可以以任何大小写形式输出答案。例如，字符串 $\rm{yEs}$ 、 $\rm{yes}$ 和 $\rm{Yes}$ 都将被视为肯定的回答。 `您可以以任何大小写形式输出答案。例如，字符串 $\rm{yEs}$、$\rm{yes}$ 和 $\rm{Yes}$ 都将被视为肯定的回答。`

样例与数据规范

类目	编号	规则描述
样例	D01	在不暴露核心算法/坑点的前提下，除非某分支存在任何一个样例都会暴露核心算法/坑点，否则每一个分支都需要提供一组样例。是否类逻辑判定题需提供 `YES/NO` 的判断各至少一组。博弈类题目需提供先手胜利和后手胜利的样例输入/输出各至少一组。
	D02	每个题目至少需要提供两个样例，对于简单问题（周赛前四题、小白月赛前四题、练习赛前两题），最好提供更多示例。
	D03	如题目包含多解，构造一个多解的样例，并展示至少两个正确的答案。
	D04	除非任何有意义的样例都会暴露核心算法，否则，禁止提供无意义的样例输入/输出。
	D05	提供尽可能多的样例解释，对于简单问题（周赛前四题、小白月赛前四题、练习赛前两题），应提供更多、更详细的样例解释。
数据规范	D06	禁止测试数据对标程友好，必须包含将标程卡到最大复杂度的测试数据。细则该条规则重点针对于剪枝优化。对于您的标程中使用的任何一个剪枝，您都需要考虑是否存在这样的极限构造，导致您的剪枝力度降低乃至失效。避免因为数据弱，导致标程中存在错误的强力剪枝。如果你无法证明剪枝的正确性、也无法构造出恰当的极限数据，去除不必要的剪枝。当且仅当您能够证明剪枝的正确性、经过极限数据的测试、添加剪枝后依旧符合您的预期难度标准，才能够在标程中使用该剪枝；否则，我们都不建议您使用剪枝。
	D07	如果测试点总数合理，请以全排列的形式添加所有可能的小测试点。
	D08	数据应当包含每个变量的最小可能值、最大可能值以及中间值。
	D09	您应当熟悉基础的构造知识，至少需要针对错解、偏解构造出对应的树/图/网络的样例，例如，长链、二叉树、网格图、菊花图、毛毛虫图等等。如果你对此不熟练或有疑问，请务必与协调员沟通。细则我们期望的数据集中至少应当包含菊花图（浅深度）、带链图（长深度）、Prüfer 序列生成树（期望 $\sqrt n$ 深度）和随机图（期望 $\log$ 深度）。这一般用于防止暴力通过。对于最短路题，我们期望的数据集中至少应当包含一组卡死不当使用 SPFA 获取超额复杂度的特殊构造。您可以参考为了激励并推广卡 SPFA 这一行为，我提供一种最简单的卡 SPFA 的方法。对于网络流的题目，我们期望的数据集中至少应当包含一组卡死 EK 算法的特殊构造。并尽可能的在较小的范围内构造能将 Dinic 算法卡到最大复杂度的样例，而不是一味的增加数据范围。
	D10	如果必要，请书写程序使得可能的暴力算法（如分块、搜索剪枝）、随机算法（如模拟退火）和错解不能通过。
	D11	您需要同时保证数据范围、格式的合法。例如，数据是同一行给出、或是分行给出；文件结尾处是否存在多余数据等等。
	D12	至少使用一种被广泛认可的方式检测数据是否合法。我们强烈建议您建议使用 `testlib.h` 加以验证（您可以参考 OI-Wiki 了解这个专为竞赛出题设计的库）；当然，使用 `Python` 的 `assert` 等函数处理也能被认可，但是我们并不推荐；`C++` 的 `std::assert` 函数处理无法被认可，因为其不包含空格/换行检查。
	D13	对于涉及到实数的题目（如计算几何、三分算法），构造出的任何边界数据都要求至少大于 10 倍 `EPS` 以上。细则例如，对于平面上三点 $A,B,C$ ，你应当确保斜率 $\|k(A,B)-k(B,C)\| \geq 10 \times {\rm EPS}$ 。

标程规范

类目	编号	规则描述
标程选择	E01	唯一确定一份符合当前题目难度基准、大部分选手都会这样书写的做法作为标程。即便有多种不同复杂度的做法、或存在剪枝优化，都只能作为参考。
	E02	标程应当在不使用任何常数优化的情况下编写。`C++` 标程禁止使用火车头、禁止使用内联汇编、禁止使用与平台相关的指令集优化、禁止使用读入优化。细则火车头通常指 `C++` 选手在比赛时使用的 `C++` 编译器优化选项，例如 `-O2` 、 `-O3` 、 `-Ofast` 等。在简单问题（周赛前四题、小白月赛前四题、练习赛前两题）的标程中，关闭同步流的技巧也不应当被使用。在 `C++` 中使用 `getchar()` 通常不被认为是读入优化，因为在默认优化开关下，此优化不一定总是产生正收益，故仅作为出题人编码习惯处理。 `int read() { int s = 0; char x = getchar(); while (x < '0' \|\| x > '9') { x = getchar(); } while (x >= '0' && x <= '9') { s = s * 10 + x - '0'; x = getchar(); } return s; }`
	E03	对于简单问题（周赛前四题、小白月赛前四题、练习赛前两题），必须保证至少 `PyPy` 能够通过，尽可能保证 `Python` 能够通过。您应当使用 `Python` 编写一个没有任何优化的解决方案（可以是自己编写、使用 ChatGPT 等 AI 工具转译，或是求助于协调员），并进行测试。如果 `Python` 无法通过，您需要在题目中标注。参考格式在几乎全部的情况下，`PyPy` 的运行速度优于 `Python` ，我们建议您选择对应版本的 `PyPy` 进行提交、而不是 `Python` 。 `在几乎全部的情况下，$\sf PyPy$ 的运行速度优于 $\sf Python$ ，我们建议您选择对应版本的 $\sf PyPy$ 进行提交、而不是 $\sf Python$ 。`
	E04	如果使用 `C / C++ / Rust / Pascal` 等小常数语言编写标程，则至少应当保证 `Python` 和 `Java` 的其中一种可以通过题目。
	E05	除经典数学结论/定理/公理/猜想外，对于所给定的数据范围，必须要在有严格证明或暴力程序验证的情况下，才能使用结论。
时空限制	E06	标程运行不得超过一半的时间限制和一半的空间限制。禁止以"某道题目是难题"为由，将时间空间卡的特别死。
	E07	如无关预期解法，不得进行任何的空间限制。对于简单问题（周赛前四题、小白月赛前四题、练习赛前两题），我们推荐您使用 256MB 及以上的空间限制；对于复杂问题，我们推荐您使用 512MB 及以上的空间限制。如有必要，您可以向协调员申请更大的空间限制。
	E08	如果您的预期解法需要限制空间，我们建议的最低空间限制为 64MB ，否则可能会导致 `Java` 等语言无法通过。若需要限制为更小的空间，请在题面中注明，并测试是否存在无法通过的语言，如有，则一并注明。
	E09	NP 问题带有剪枝的标程，必须证明存在上界（无需保证上确界）满足最大范围数据的复杂度需求。

高频 LaTeX 语法答疑

我们建议您使用 LaTeX公式编辑器 进行在线编辑。

如果您能手绘出形状但是不知道其对应的 $\LaTeX$ 语法，我们建议您使用 Detexify 进行手绘识别。

任何时候，如果您有 $\LaTeX$ 语法上的疑问，欢迎您与我们的协调员联系。

名称	输入	显示	说明
上标	`12^1` 、`12^{12}`	$12^{12}$ 、 $12^1$	单个数字时花括号可以省略
下标	`a_1` 、`a_{12}`	$a_{12}$ 、 $a_1$	单个数字时花括号可以省略
行高扩展	`\displaystyle`	-	该命令可以使得数学公式在行内显示时，完整的展开，而不是局限于当前行高度
大括号	`\{a_1\}`	$\{a_1\}$	请参考 `12`
自动匹配高度的括号	`\left( a^{12^{12}} \right)`	$\left( a^{12^{12}} \right)$	根据公式高度自动匹配括号大小
手动匹配高度的括号	`\big( \Big( \bigg( \Bigg(`	$\big( \Big( \bigg( \Bigg($	手动匹配括号大小
较大形式的组合数	`\dbinom{n}{m}`	$\dbinom{n}{m}$	不要使用诸如 $C^{m}_{n}$ 、 $C(n,m)$
较小形式的组合数	`\tbinom{n}{m}` 或 `\binom{n}{m}`	$\tbinom{n}{m}$ 、 $\binom{n}{m}$
取模	`12 \bmod 3`	$12 \bmod 3$	不加 `b` 会多一个丑陋的空格
集合分隔号	`\vert` 、`\	`（斜杠加键盘上的竖）	$\vert$ 、 $\\|$
大分数	`\dfrac{a+b+c}{2}`、 `\displaystyle\frac{a+b+c}{2}`	$\displaystyle \frac{a b c}{2}$	后者是通用的
小分数	`\tfrac{a+b+c}{2}`	$\tfrac{a b c}{2}$	牛客一般会自动给你的公式添加行高扩展，如果你不希望被这样对待，使用这个强制固定行高
大累加	`\sum\limits_{i=1}^n` 、`\displaystyle \sum_{i=1}^n`	$\sum\limits_{i=1}^n$ 、 $\displaystyle \sum_{i=1}^n$	前者占用的空间更小
乘法	`\cdot` 、`\times`	$2 \cdot 10^5$ 、 $2 \times 10^5$	数学上推荐使用前者，但后者看起来更清晰
省略号	`\dots`	$a_1,a_2,\dots,a_n$	不应该使用中文省略号
百分号	`\%`	$10\%$	不要使用 `%`
小空格	`\,`	$114\,514$	通常用于千分位间隔
中空格	`\`	$a \ b$	通常用于公式中增加可读性
自定义空格	`\hspace{15pt}`	$a \hspace{15pt} b$	通常用于模拟中文中的缩进，两个中文汉字推荐使用 `15pt` ，因为 `pt` 能够自动根据当前网页 CSS 状态和字体大小自动调整；而 15 在牛客上显示效果近似于两个中文汉字
同余	`q \equiv 1 \pmod{M}`	$q \equiv 1 \pmod{M}$
异或	`\oplus` 、`\bigoplus`	$a \oplus b$ 、 $a \bigoplus b$	后者用于求和
整除	`\mid`	$a \mid b$	会在符号前后添加一个小空格，增加可读性；不建议您使用键盘上的竖
不整除	`\nmid`	$a \nmid b$
度	`^{\circ}` 、`\degree`	$90^\circ$ 、 $90\degree$	后者可能仅适用于部分版本
无穷大	`\infty`	$\infty$
约等于	`\approx`	$a \approx b$
矩阵	`\begin{bmatrix} a & b \\ c & d \end{bmatrix}`	$\begin{bmatrix} a$	矩阵的行与行之间用 `\\` 分隔，列与列之间用 `&` 分隔
正体操作	`\gcd` 、`\min` 、`\max`	$\gcd(a,b)$ 、 $\min(a,b)$ 、 $\max(a,b)$
正体操作符	`\operatorname{lcm}(1,2)` 、`{\rm lcm}(1,2)`	$\operatorname{lcm}(1,2)$ 、 ${\rm lcm}(1,2)$	建议使用前者
左箭头	`\gets` 、`\leftarrow`	$\gets$ 、 $\leftarrow$	通常用于赋值
右箭头	`\to` 、`\rightarrow`	$\to$ 、 $\rightarrow$
波浪线	`\sim`	$\sim$	通常用于表示范围

完整题干参考格式（仅供参考）

对于给定的 $h$ 行 $w$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。每个方格要么是可以通过的空方格 $\sf 0$ ，要么是不可通过的墙方格 $\sf 1$ ，特别的，网格的四周都是墙方格，你可以沿着空方格上下左右随意移动：从 $(x,y)$ 向上移动一格即抵达 $(x-1,y)$ 、向下移动一格即抵达 $(x 1,y)$ 、向左移动一格即抵达 $(x,y-1)$ 、向右移动一格即抵达 $(x,y 1)$ 。

保证起点和终点一定为空方格，你始终可以找到一条从起点出发到达终点的可行路径。

在这里，当 $|x-x'| |y-y'|=1$ 时，单元格 $(x,y)$ 和 $(x',y')$ 被认为是相邻的。

对于给定的 $h$ 行 $w$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。每个方格要么是可以通过的空方格 $\sf 0$ ，要么是不可通过的墙方格 $\sf 1$ ，特别的，网格的四周都是墙方格，你可以沿着空方格上下左右随意移动：从 $(x,y)$ 向上移动一格即抵达 $(x-1,y)$ 、向下移动一格即抵达 $(x+1,y)$ 、向左移动一格即抵达 $(x,y-1)$ 、向右移动一格即抵达 $(x,y+1)$ 。
保证起点和终点一定为空方格，你始终可以找到一条从起点出发到达终点的可行路径。
在这里，当 $|x-x'|+|y-y'|=1$ 时，单元格 $(x,y)$ 和 $(x',y')$ 被认为是相邻的。

【子序列】子序列为从原数组中删除任意个（可以为零、可以为全部）元素得到的新数组。

【子数组】子数组为从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

【数组公共子序列】如果数组 $a$ 的一个子序列 $a'$ 与数组 $b$ 的一个子序列 $b'$ 完全相等，那么子序列 $a',b'$ 是数组 $a,b$ 的一个公共子序列。

【子序列】子序列为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

【子串】子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

【子序列】<u>子序列</u>为从原数组中删除任意个（可以为零、可以为全部）元素得到的新数组。
【子数组】<u>子数组</u>为从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。
【数组公共子序列】如果数组 $a$ 的一个子序列 $a'$ 与数组 $b$ 的一个子序列 $b'$ 完全相等，那么子序列 $a',b'$ 是数组 $a,b$ 的一个<u>公共子序列</u>。
【子序列】<u>子序列</u>为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。
【子串】<u>子串</u>为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

【反转】反转就是将数组从右往左重新书写，例如 $\{a_1,a_2,\dots,a_n\}$ 反转后得到 $\{a_n,a_{n-1},\dots,a_1\}$ 。

【反转】反转就是将字符串从右往左重新书写，例如 $s_1s_2\dots s_n$ 反转后得到 $s_n s_{n-1} \dots s_1$ 。

【反置】若当前字符为 $\tt 0$ ，反置后为 $\tt 1$ ；若当前字符为 $\tt 1$ ，反置后为 $\tt 0$ 。

【中位数】长度为 $n$ 的数组 $\{a_1,a_2,\cdots,a_n\}$ ，其中位数为将所有元素从小到大排列后，位于中间的数。特别地，当 $n$ 为偶数时，中位数为中间两个数的平均值。例如，数组 $\{2,3,1,5,4\}$ 的中位数是 $3$ ，数组 $\{1,3,2,6,4,5\}$ 的中位数是 $3.5$ 。

【回文串】一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

【循环替换】将字符串中的某一个字符替换为字母表中的下一个字母（即小写字母 $\texttt{a-z}$ 循环替换为下一个小写字母，大写字母 $\texttt{A-Z}$ 循环替换为下一个大写字母），称之进行了一次循环替换。特别的， $\texttt{$ 将会被替换为 $\texttt{$ 、 $\texttt{$ 将会被替换为 $\texttt{$ 。

【反转】<u>反转</u>就是将数组从右往左重新书写，例如 $\{a_1,a_2,\dots,a_n\}$ 反转后得到 $\{a_n,a_{n-1},\dots,a_1\}$ 。
【反转】<u>反转</u>就是将字符串从右往左重新书写，例如 $s_1s_2\dots s_n$ 反转后得到 $s_n s_{n-1} \dots s_1$ 。
【反置】若当前字符为 $\tt 0$ ，<u>反置</u>后为 $\tt 1$ ；若当前字符为 $\tt 1$ ，反置后为 $\tt 0$ 。
【中位数】长度为 $n$ 的数组 $\{a_1,a_2,\cdots,a_n\}$ ，其<u>中位数</u>为将所有元素从小到大排列后，位于中间的数。特别地，当 $n$ 为偶数时，中位数为中间两个数的平均值。例如，数组 $\{2,3,1,5,4\}$ 的中位数是 $3$ ，数组 $\{1,3,2,6,4,5\}$ 的中位数是 $3.5$ 。
【回文串】一个字符串被称作<u>回文串</u>，当且仅当这个字符串从左往右读和从右往左读是相同的。
【循环替换】将字符串中的某一个字符替换为字母表中的下一个字母（即小写字母 $\texttt{a-z}$ 循环替换为下一个小写字母，大写字母 $\texttt{A-Z}$ 循环替换为下一个大写字母），称之进行了一次<u>循环替换</u>。特别的，$\texttt{"z"}$ 将会被替换为 $\texttt{"a"}$ 、$\texttt{"Z"}$ 将会被替换为 $\texttt{"A"}$ 。

【字典序】字符的字典序即其对应的 $\sf Ascii$ 码（ $\tt A < \cdots < Z < a < \cdots < z$ ）。

【狭义的字典序比较】从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的字母表顺序得出字符串的大小，称为字典序比较。

【广义的字典序比较】从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的 $\sf Ascii$ 码大小得到字符串的大小，称为字典序比较。例如，字符串 $\texttt{$ 和 $\texttt{$ 比较时，由于第一个字符不相同，所以 $\texttt{$ 。

【字典顺序比较】从数组的第一个元素开始逐个比较，直到找到第一个不同的位置，通过比较这个位置元素的大小得出数组的大小，称为字典顺序比较。

【字典序】字符的<u>字典序</u>即其对应的 $\sf Ascii$ 码（ $\tt A < \cdots < Z < a < \cdots < z$ ）。
【狭义的字典序比较】从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的字母表顺序得出字符串的大小，称为<u>字典序比较</u>。
【广义的字典序比较】从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的 $\sf Ascii$ 码大小得到字符串的大小，称为<u>字典序比较</u>。例如，字符串 $\texttt{"10"}$ 和 $\texttt{"2"}$ 比较时，由于第一个字符不相同，所以 $\texttt{"10"} < \texttt{"2"}$ 。
【字典顺序比较】从数组的第一个元素开始逐个比较，直到找到第一个不同的位置，通过比较这个位置元素的大小得出数组的大小，称为<u>字典顺序比较</u>。

【排列】长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

第一行输入一个整数 $n\ (1 \leqq n \leqq 10^5)$ 代表排列中的元素数量。

第二行输入 $n$ 个互不相同的整数 $a_1,a_2,\cdots,a_n\ (1 \leqq a_i \leqq n)$ 代表排列元素。

【排列】长度为 $n$ 的<u>排列</u>是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，$\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
第一行输入一个整数 $n\ (1 \leqq n \leqq 10^5)$ 代表排列中的元素数量。
第二行输入 $n$ 个互不相同的整数 $a_1,a_2,\cdots,a_n\ (1 \leqq a_i \leqq n)$ 代表排列元素。

【合法的括号序列】如果在括号序列中插入字符 $\texttt{ }$ 和 $\tt 1$ 就可以得到正确的算术表达式，那么这个括号序列就称为合法的括号序列。例如， $\texttt{$ 、 $\texttt{$ 和 $\texttt{$ 是合法的括号序列，因为填入内容后可以表示为 $\texttt{$ 、 $\texttt{$ 和 $\texttt{$ 。

更严格地，一个括号序列被称为合法的括号序列，当且仅当：

空串是合法的括号序列；
如果 $A$ 是合法的括号序列，那么 $\texttt{$ 也是合法的括号序列；
如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是合法的括号序列。

【合法的括号序列】如果在括号序列中插入字符 $\texttt{+}$ 和 $\tt 1$ 就可以得到正确的算术表达式，那么这个括号序列就称为<u>合法的括号序列</u>。例如，$\texttt{""}$、$\texttt{"(())"}$ 和 $\texttt{"()()"}$ 是合法的括号序列，因为填入内容后可以表示为 $\texttt{"1"}$ 、$\texttt{"((1))"}$ 和 $\texttt{"(1)+(1)"}$ 。
更严格地，一个括号序列被称为<u>合法的括号序列</u>，当且仅当：
1. 空串是合法的括号序列；
2. 如果 $A$ 是合法的括号序列，那么 $\texttt{"(}A\texttt{)"}$ 也是合法的括号序列；
3. 如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是合法的括号序列。

完整输入输出参考格式（仅供参考）

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^4\right)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 $n\left(1 \leq n \leq 10^5\right)$ 代表数组中的元素数量。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n\left(0\leq a_i \leq 2 \times 10^6\right)$ 代表数组元素。

第三行输入一个小数点后位数不超过 $6$ 位的实数 $p$ 代表概率。

除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$ 。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^4\right)$ 代表数据组数，每组测试数据描述如下：
第一行输入一个整数 $n\left(1 \leq n \leq 10^5\right)$ 代表数组中的元素数量。
第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n\left(0\leq a_i \leq 2 \times 10^6\right)$ 代表数组元素。
第三行输入一个小数点后位数不超过 $6$ 位的实数 $p$ 代表概率。
除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$ 。

对于每一组测试数据，在单独的一行上输出一个整数，代表答案。由于答案可能很大，请将答案对 $(10^9 7)$ 取模后输出。

对于每一组测试数据，在单独的一行上输出一个整数，代表答案。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

在一行上输入一个长度为 $n$ ，且只由 $\tt 0$ 和 $\tt 1$ 构成的字符串 $s_1$ 。

在一行上输入一个长度为 $n$ ，且只由小写字母构成的字符串 $s_2$ 。

在一行上输入一个长度为 $n$ ，且由大小写字母、数字和空格混合构成的字符串 $s_3$ 。

在一行上输入一个长度为 $n$ ，且只由 $\tt 0$ 和 $\tt 1$ 构成的字符串 $s_1$ 。
在一行上输入一个长度为 $n$ ，且只由小写字母构成的字符串 $s_2$ 。
在一行上输入一个长度为 $n$ ，且由大小写字母、数字和空格混合构成的字符串 $s_3$ 。

由于实数的计算存在误差，当误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\tfrac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$ 时，您的答案将被接受。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

如果答案存在，在一行上输出 $\rm YES$ ；否则，直接输出 $\rm NO$ 。

可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出 $p$ 和 $q$ 。

由于实数的计算存在误差，当误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\tfrac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$ 时，您的答案将被接受。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
如果答案存在，在一行上输出 $\rm YES$ ；否则，直接输出 $\rm NO$ 。
可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出 $p$ 和 $q$ 。

可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \cdot q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998,244,353$ ， $q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。因为 $3 \times 333333336 \equiv 1 \pmod{M}$ ，我们应该输出 $2 \times 333333336 \bmod M = 666666672$ 。

可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \cdot q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998,244,353$ ，$q^{-1}$ 是满足 $q\times q^{-1}  \equiv 1 \pmod{M}$ 的整数。
因为 $3 \times 333333336 \equiv 1 \pmod{M}$ ，我们应该输出 $2 \times 333333336 \bmod M = 666666672$ 。

第一行输入两个整数 $r,c\left(1 \leq r, c \leq 10^6;\ 1 \leq r \times c \leq 10^{6}\right)$ 代表矩阵的行数和列数。

此后 $r$ 行, 第 $i$ 行输入一个长度为 $c$ ，仅由 $\tt 0$ 和 $\tt 1$ 两个字符构成的字符串 $s$ 用于描述矩阵的第 $r$ 行。

第一行输入两个整数 $r,c\left(1 \leq r, c \leq 10^6;\  1 \leq r \times c \leq 10^{6}\right)$ 代表矩阵的行数和列数。
此后 $r$ 行, 第 $i$ 行输入一个长度为 $c$ ，仅由 $\tt 0$ 和 $\tt 1$ 两个字符构成的字符串 $s$ 用于描述矩阵的第 $r$ 行。

此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leqq u_i, v_i \leqq n;\ u_i \neq v_i)$ 表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证树连通。

此后 $m$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leqq u_i, v_i \leqq n;\ u_i \neq v_i)$ 表示图上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证图连通，没有重边。

此后 $n-1$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leqq u_i, v_i \leqq n;\ u_i \neq v_i)$ 表示树上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证树连通。
此后 $m$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i\ (1 \leqq u_i, v_i \leqq n;\ u_i \neq v_i)$ 表示图上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证图连通，没有重边。

名词解释：数学（仅供参考）

【极差】数组的极差定义为数组中最大值和最小值的差。
【MEX】整数数组的 $\operatorname{mex}$ 定义为没有出现在数组中的最小非负整数。例如 $\operatorname{mex} \{1,2,3 \} =0$ 、 $\operatorname{mex} \{0,2,5\} =1$ 。
【单调不降】单调不降是指对于对于数组 $a$ 中从左向右数的第 $i$ 个元素 $a_i$ ，如果 $a_{i 1}$ 存在，那么 $a_i \le a_{i 1}$ 。
【交换】选取两个不同的下标 $i,j\ (1 \le i < j \le n)$ ，将 $a_i$ 与 $a_j$ 位置互换，称为一次交换操作。
【矩阵】 $\begin{bmatrix}1$
【上下取整】在这里， $\lfloor x \rfloor$ 代表对 $x$ 进行下取整操作； $\lceil x \rceil$ 代表对 $x$ 进行上取整操作。
【异或】在这里， $\oplus$ 表示按位异或操作。
【gcd】 $\gcd$ ，即最大公因数，指两个整数共有约数中最大的一个。例如， $12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此 $\gcd(12,30)=6$ 。

1. 【极差】数组的<u>极差</u>定义为数组中最大值和最小值的差。
2. 【MEX】整数数组的 $\operatorname{mex}$ 定义为没有出现在数组中的最小非负整数。例如 $ \operatorname{mex} \{1,2,3 \} =0$ 、$ \operatorname{mex} \{0,2,5\} =1$ 。
3. 【单调不降】<u>单调不降</u>是指对于对于数组 $a$ 中从左向右数的第 $i$ 个元素 $a_i$ ，如果 $a_{i+1}$ 存在，那么 $a_i \le a_{i+1}$ 。
4. 【交换】选取两个不同的下标 $i,j\ (1 \le i < j \le n)$ ，将 $a_i$ 与 $a_j$ 位置互换，称为一次交换操作。
5. 【矩阵】$\begin{bmatrix}1  & 0 & \cdots  & 0\\0  & 1 & \cdots & 0\\\vdots  & \vdots & \ddots  & \vdots \\0  & 0 & \cdots & 1\end{bmatrix}$
6. 【上下取整】在这里，$\lfloor x \rfloor$ 代表对 $x$ 进行下取整操作；$\lceil x \rceil$ 代表对 $x$ 进行上取整操作。
7. 【异或】在这里，$\oplus$ 表示按位异或操作。
8. 【gcd】$\gcd$ ，即最大公因数，指两个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此 $\gcd(12,30)=6$ 。

名词解释：图论（仅供参考）

【树】树是指这样的一张图，其由 $n$ 个节点和 $n-1$ 条边构成，其上的任意两个点都连通，且不存在环。
【森林】 $m\ (m≥0)$ 棵互不相交的树的集合。
【生成树】对于一张 $n$ 个节点的图，任选其中 $n-1$ 条边，使得所有点连通，这些边会组成一棵树，称为这张图的一棵生成树。
【树上连通块】对于树上的两个点，如果它们相互连通，则称他们位于同一个连通块里。
【联通块】对于图上的两个点，如果它们相互连通，则称他们位于同一个连通块里。
【度】与一个顶点相连接的边的条数称为该顶点的度。
【叶子节点】如果一个节点有且仅有一个节点与之相连，那么这个点就是一个叶子节点。
【二叉树】
1. 每个节点要么没有父节点 $\tt ^1$ 连接（此时该节点被称为根节点 $\tt ^2$ ）、要么被 $1$ 个父节点连接（此时该节点被称为父节点的子节点 $\tt ^3$ ）；
2. 每个节点连接的子节点数量要么为 $0$ （此时该节点被称为叶子节点 $\tt ^4$ ）、要么小于等于 $2$ ；
3. 对于一个节点，其父节点、父节点的父节点、……都称为它的祖先节点 $\tt ^5$ 。
【二叉平衡树】
1. 某个非叶子节点 $\tt ^3$ 的左子节点 $\tt ^2$ 的权值小于当前节点的权值；
2. 某个非叶子节点 $\tt ^3$ 的右子节点 $\tt ^2$ 的权值大于当前节点的权值；
3. 任意两个叶子节点 $\tt ^3$ 的深度差都小于等于 $1$ 。
【完全二叉树】是指一棵高度为 $h$ 的二叉树，其 $1$ 到 $h-1$ 层的节点都达到最大个数（即 $1\sim h-1$ 层为满二叉树），第 $h$ 层的节点都集中在在最左边。
【二分图、完全二分图】二分图是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 $U$ 与 $V$ ，使得图中的每一条边都连接 $U$ 中的一个节点与 $V$ 中的一个节点。如果 $U$ 与 $V$ 中节点的数量相同，则称这张图为平衡二分图。
【匹配、最大匹配、匹配数】无向图的匹配是一个边的集合，其中任意两条边都没有共同的端点。图的最大匹配是一个包含了最多条边的匹配。图的匹配数是这张图的最大匹配所包含的边的数量。

1. 【树】<u>树</u>是指这样的一张图，其由 $n$ 个节点和 $n-1$ 条边构成，其上的任意两个点都连通，且不存在环。
2. 【森林】$m\ (m≥0)$ 棵互不相交的树的集合。
3. 【生成树】对于一张 $n$ 个节点的图，任选其中 $n-1$ 条边，使得所有点连通，这些边会组成一棵树，称为这张图的一棵<u>生成树</u>。
4. 【树上连通块】对于树上的两个点，如果它们相互连通，则称他们位于同一个<u>连通块</u>里。
5. 【联通块】对于图上的两个点，如果它们相互连通，则称他们位于同一个<u>连通块</u>里。
6. 【度】与一个顶点相连接的边的条数称为该顶点的<u>度</u>。
7. 【叶子节点】如果一个节点有且仅有一个节点与之相连，那么这个点就是一个<u>叶子节点</u>。
8. 【二叉树】
   1. 每个节点要么没有<u>父节点</u>$\tt ^1$连接（此时该节点被称为<u>根节点</u>$\tt ^2$）、要么被 $1$ 个父节点连接（此时该节点被称为父节点的<u>子节点</u>$\tt ^3$）；
   2. 每个节点连接的子节点数量要么为 $0$ （此时该节点被称为<u>叶子节点</u>$\tt ^4$）、要么小于等于 $2$ ；
   3. 对于一个节点，其父节点、父节点的父节点、……都称为它的<u>祖先节点</u>$\tt ^5$。
9. 【二叉平衡树】
   1. 某个非<u>叶子节点</u>$\tt ^3$的左<u>子节点</u>$\tt ^2$的权值小于当前节点的权值；
   2. 某个非<u>叶子节点</u>$\tt ^3$的右<u>子节点</u>$\tt ^2$的权值大于当前节点的权值；
   3. 任意两个<u>叶子节点</u>$\tt ^3$的深度差都小于等于 $1$ 。
10. 【完全二叉树】是指一棵高度为 $h$ 的二叉树，其 $1$ 到 $h-1$ 层的节点都达到最大个数（即 $ 1\sim h-1 $ 层为满二叉树），第 $h$ 层的节点都集中在在最左边。
11. 【二分图、完全二分图】<u>二分图</u>是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 $U$ 与 $V$ ，使得图中的每一条边都连接 $U$ 中的一个节点与 $V$ 中的一个节点。如果 $U$ 与 $V$ 中节点的数量相同，则称这张图为<u>平衡二分图</u>。
12. 【匹配、最大匹配、匹配数】无向图的<u>匹配</u>是一个边的集合，其中任意两条边都没有共同的端点。图的<u>最大匹配</u>是一个包含了最多条边的匹配。图的<u>匹配数</u>是这张图的最大匹配所包含的边的数量。