本题没有可用的提交语言。

描述

在当代超大规模集成电路（VLSI）芯片行业中，电气工程师使用的软件工具会执行许多优化操作。你的任务是实现芯片设计中的一种特定优化。你的工具会接收一个由与非门（NAND gate，其输出值为输入值的否定合取，即当且仅当两个输入值均为$1$时，输出值为$0$）构成的无环网络。该网络是已合成组件的一部分，无法更改。网络的所有输入都连接到一个信号$x$。目标是将某些输入与$x$断开，并将常量信号$0$和/或$1$分配给这些输入，同时确保设计实现的功能保持不变。

我们称对网络输入的$x$、$0$和/或$1$的分配为最优，如果连接到$x$的输入数量尽可能少，但网络计算的功能仍与所有输入都连接到$x$时相同。

示例
观察以下设计。

我们可以将其更改为仅有一个变量输入的设计，例如：

（注意，还存在其他方式将输入连接到仅一个$x$和某些$0$或$1$，同时实现相同的功能）。

任务
编写一个程序，对每个数据集：
读取网络的描述，
计算对网络输入的$x$、$0$和/或$1$的最优分配，
输出结果。

输入

输入的第一行包含一个正整数$d$，表示数据集的数量，$1 \leq d \leq 20$。接下来是数据集。

每个数据集由两行组成。第一行包含两个正整数$n$和$m$，用单个空格分隔，$1 \leq n \leq 100000$，$1 \leq m \leq 200000$。整数$n$是网络的输入数量，$m$是网络中门的数量。

第二行包含$2m$个非零整数，用单个空格分隔。第$2j - 1$和第$2j$位置的数字描述了门$j$的输入信号源。正数$s$表示门$s$的输出，负数$s$表示网络的第$(-s)$个输入。门和网络输入的编号从$1$开始。每个门的输入连接到网络的输入或之前描述的门输出。每个网络输入至少连接到一个门输入。每个门输出至少连接到一个门输入，除了最后一个门的输出连接到网络的输出。

输出

输出应包含$d$行，每行对应一个数据集。第$i$行应包含第$i$个数据集的答案。

对一个数据集的答案应包含一个长度为$k$的字符序列，以换行符结束（中间无空格）。每个字符应为$0$（数字“零”）、$1$（数字“一”）或$x$（小写字母“x”）。序列的第$i$个符号表示对第$i$个网络输入的分配。

如果存在多个最优分配，则程序可以输出其中任意一个（但仅输出一个）。

输入数据 1

1
3 6
-1 -3 -1 -2 1 2 1 2 4 3 5 5

输出数据 1

10x

来源

中欧 2001