给定一个包含 $n$ 个顶点和 $m$ 条边的无向图，其中第 $i$ 个顶点有一个限制 $a_i$，请为每条边指定一个方向，使图变为有向图，并最小化以下值 $D$：

$$D = \sum_{i=1}^{n} \max(0, d_i - a_i)$$

其中 $d_i$ 是第 $i$ 个顶点的入度（即指向该顶点的边数）。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 300, 1 \le m \le 300$)，分别表示顶点数和边数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^4$)，其中 $a_i$ 表示第 $i$ 个顶点的限制。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示连接顶点 $u_i$ 和 $v_i$ 的一条边。注意图中可能存在自环或重边。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $3 \times 10^3$。

输出格式

对于每组测试数据，输出两行。第一行包含一个整数，表示 $D$ 的最小值。第二行包含一个长度为 $m$ 的字符串 $s_1s_2 \dots s_m$，仅由 '0' 和 '1' 组成，表示实现最小 $D$ 的边方向分配方案。如果 $s_i = '0'$，则第 $i$ 条边从 $u_i$ 指向 $v_i$；否则，它从 $v_i$ 指向 $u_i$。如果存在多种合法的方案，输出其中任意一种即可。

样例

输入 1

2
4 5
0 1 1 5
1 2
1 3
2 3
3 2
4 4
3 2
0 0 2
1 3
3 2

输出 1

2
01001
0
01

说明

第一个样例测试数据的情况如下图所示：