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. D = \sum\limits_{i=1}^n \max(0, d_i - a_i) 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 0s and 1s indicating a direction assignment plan of the edges to achieve the smallest possible . If then the -th edge is going from into ; Otherwise it's going from into . If there are multiple valid answers you can output any of them.
:::