题目描述

给出一张包含 $n$ 个结点，$m$ 条边的简单无向图$^\texttt{[1]}$（可能不连通），点的颜色用一个长为 $n$ 的 $\underline{\tt{01}}$ 串$^\texttt{[2]}$ $s = s_1s_2\dots s_n$ 表示，如果 $s_i = \texttt{0}$，$i$ 号结点为白色；如果 $s_i = \texttt{1}$，$i$ 号结点为黑色。 你可以点亮若干个结点（可以不点亮）。定义一个点的价值为：所有与其直接相连的被点亮的结点的数量。定义整张图的价值为所有白色结点的总价值减去黑色结点的总价值。 你需要给出一种点亮方案，其能够最大化整张图的总价值。 形式化题意： $\hspace{23pt}\bullet\,$给定一张简单无向图 $G=(V,E)$，其中每个点有黑白两种颜色，你需要为每个点附上一个点权 $c_i\in \{0,1\}$，来最大化下面式子的值： $\sum^{}_{u\ \text{is white},u\in V}\sum^{}_{(u,v)\in E}c_v - \sum^{}_{u\ \text{is black},u\in V}\sum^{}_{(u,v)\in E}c_v$ $\hspace{23pt}\bullet\,$以任意顺序输出所有点权 $c_i$ 赋为 $1$ 的点编号。 【名词解释】 简单无向图$^\texttt{[1]}$：指不包含自环（连接节点自身的边）和重边（两个节点之间存在多条边）的无向图。即任意两个不同节点之间至多只有一条边。 $\underline{\tt{01}}$ 串$^\texttt{[2]}$：只包含字符 $\tt0$ 和 $\tt1$ 的字符串。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $t\ (1\le t\le10^4)$ 代表数据组数，每组测试数据描述如下：官方中文

第一行输入两个整数 $n,m\ (1\le n\le2\times10^5;\,0\le m\le\min(\frac{n(n-1)}{2},2\times10^5))$ ，表示图的点数、边数。 第二行输入一个长度为 $n$ 的 $\texttt{01}$串 $s$，表示每个点的颜色。若 $s_i=\tt0$，则节点 $i$ 为白色；若 $s_i=\tt1$，则节点 $i$ 为黑色。 之后的 $m$ 行，第 $i$ 行输入两个整数 $u_i,v_i\ (1 \leq u_i, v_i \leq n;\ u_i \neq v_i)$ 表示图上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。保证图没有重边。官方中文

除此之外，保证单个测试文件的 $n$ 总和不超过 $2\times10^5$，$m$ 总和不超过 $2\times10^5$。官方中文

输出格式

对于每一组测试数据，输出两行：官方中文

第一行输出一个非负整数 $k\ (0\le k\le n)$ ，表示需要点亮的点的总数。 第二行输出 $k$ 个正整数 $a_1,a_2,\ldots,a_k\ (1\le a_i\le n)$ ，表示具体需要点亮的点。特殊的，如果 $k = 0$，请输出一行空行。 你可以以任意顺序输出这些点编号。你需要保证 $a_i$ 两两不同。官方中文

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