Description

Input

Output

Sample Input

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

Sample Output

5
3
1 +
2 -
2 +

Source

分析：就是二分图的最小点权覆盖问题，输出解的话，只要dfs即可。源点S，汇点T，将其余每个点拆成两个点，i和i+n，S和每一个i点连一条边，T点与每个i+n点连一条边，跑一遍最大流即可，对于输出解的情况，只要从S点开始dfs，标记走到的点即可。

代码：

//Dinic算法，复杂度O(n^2m)
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;   //记得必要的时候改成无符号
const int maxn=505;
const int maxm=1000005;
const int INF=1000000000;
struct EdgeNode
{
    int from;
    int to;
    int flow;
    int next;
}edge[maxm];
int head[maxn],cnt;
void add(int x,int y,int z)
{
    edge[cnt].from=x;edge[cnt].to=y;edge[cnt].flow=z;edge[cnt].next=head[x];head[x]=cnt++;
    edge[cnt].from=y;edge[cnt].to=x;edge[cnt].flow=0;edge[cnt].next=head[y];head[y]=cnt++;
    //printf("%d %d %d\n",x,y,z);
}

void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
}

int S,T,n,m;
int d[maxn];

bool bfs(int S,int T)
{
    int que[maxn],iq=0,top;
    memset(d,0,sizeof(d));
    d[S]=1;
    que[iq++]=S;
    for(int i=0;i<iq;i++)
    {
        top=que[i];
        if(top==T)return true;
        for(int k=head[top];k!=-1;k=edge[k].next)
        {
            if(!d[edge[k].to]&&edge[k].flow)
            {
                que[iq++]=edge[k].to;
                d[edge[k].to]=d[top]+1;
            }
        }
    }
    return false;
}

int dfs(int now,int maxf,int T)
{
    if(now==T)return maxf;
    int ret=0,f;
    for(int k=head[now];k!=-1;k=edge[k].next)
    {
        if(edge[k].flow&&d[edge[k].to]==d[now]+1)
        {
            f=dfs(edge[k].to,min(maxf-ret,edge[k].flow),T);
            edge[k].flow-=f;
            edge[k^1].flow+=f;
            ret+=f;
            if(ret==maxf)return ret;
        }
    }
    return ret;
}

int Dinic(int S,int T)
{
    int ans=0;
    while(bfs(S,T))ans+=dfs(S,INF,T);
    return ans;
}

int a[maxn],b[maxn];
bool mark[3*maxn];

void dfs_cut(int x)
{
    mark[x]=1;
    int y;
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        y=edge[i].to;
        if(edge[i].flow&&!mark[y])
            dfs_cut(y);
    }
}

int main()
{
    int i,x,y,cs;
    while(~scanf("%d%d",&n,&m))
    {
        init(); S=0; T=2*n+1;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            add(i+n,T,a[i]);
        }
        for(i=1;i<=n;i++){
            scanf("%d",&b[i]);
            add(S,i,b[i]);
        }
        for(i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            add(x,y+n,INF);
        }
        printf("%d\n",Dinic(S,T));
        memset(mark,false,sizeof(mark));
        dfs_cut(S); cs=0;
        for(i=1;i<=n;i++)if(!mark[i])cs++;
        for(i=n+1;i<=2*n;i++)if(mark[i])cs++;
        printf("%d\n",cs);
        for(i=1;i<=n;i++)if(!mark[i])printf("%d -\n",i);
        for(i=n+1;i<=2*n;i++)if(mark[i])printf("%d +\n",i-n);
    }
    return 0;
}