Given an undirected graph with vertices and edges where the -th vertex has a limit , please assign a direction for each edge so that the graph becomes directed and the following value  is minimized. where is the in-degree (that is, the number of edges going into that vertex) of the -th vertex.

输入描述:

There are multiple test cases. The first line of the input contains an integer  indicating the number of test cases. For each test case:
The first line contains two integers  and  (, ) indicating the number of vertices and edges.
The second line contains  integers  () where  indicates the limit of the -th vertex.
For the following  lines, the -th line contains two integers  and  () indicating that there is an edge connecting vertex  and . Note that there might be self loops or multiple edges.
It's guaranteed that neither the sum of  nor the sum of  of all test cases will exceed .

输出描述:

For each test case output two lines. The first line contains an integer indicating the smallest possible . The second line contains a string  of length  consisting only of `0's and `1's indicating a direction assignment plan of the edges to achieve the smallest possible . If  then the i-th edge is going from  into ; Otherwise it's going from  into . If there are multiple valid answers you can output any of them.

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

2
01001
0
01

The first sample test case is shown as follows.