#include <ctime>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <cctype>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <sstream>
#include <functional>
using namespace std;
char mat[111][111];
int n,deg[111],uk[111][111],now[111],tot;
int pa[111],num[111];
int dist[111];
int adj[111][111];
int vec[111][111],num_vec[111];
int vs[111],times,u;
int spfa()
{
    int id,ip,i,j,s,p,q;
    for(i=0;i<=n;i++)
         num_vec[i]=0;
    for(i=0;i<n;i++)
    {
        dist[i]=now[i]+deg[i]; 
        pa[i]=-1;
        vec[now[i]+deg[i]][num_vec[now[i]+deg[i]]++]=i;
    } 
    times++;
    while(true)
    {
        for(;u>=0;u--)
        {
            while(num_vec[u]>0)
            {
                id=vec[u][num_vec[u]-1];
                if(vs[id]!=times)
                   break;
                num_vec[u]--;
            }
            if(num_vec[u]>0)
                break;
        }
        if(u<0)
           return -1;
        num_vec[u]--;
        vs[id]=times;
        for(j=0;j<num[id];j++)
        {
            ip=adj[id][j];
            if(dist[ip]<dist[id]&&uk[id][ip]==0)
            {
                dist[ip]=dist[id];
                pa[ip]=id;
                if(dist[ip]>=now[ip]+deg[ip]+2)
                    return ip;
                vec[dist[ip]][num_vec[dist[ip]]++]=ip;
            }
        }
    }
}
int main()
{
    int i,j,s,p,q,id,ip,dk;
    while(scanf("%d",&n)==1)
    {
        tot=n*(n-1)*(n-2)/6;
        for(i=0;i<n;i++)
            deg[i]=now[i]=num[i]=0;
        for(i=0;i<n;i++)
          for(j=0;j<n;j++)
          {
             mat[i][j]=getchar();
             while(mat[i][j]<'0'||mat[i][j]>'9')
                 mat[i][j]=getchar();
              if(i==j)
                 continue;
              if(mat[i][j]=='0')
                 deg[i]++;
              else if(mat[i][j]=='2')
              {
                 if(i<j)
                 {
                      uk[i][j]=rand()%2;
                      uk[j][i]=1-uk[i][j]; 
                      if(uk[i][j]==0) 
                         now[i]++;
                      else
                         now[j]++;
                 }
                 adj[i][num[i]++]=j;
              }
          }
        u=n;
        while(true)
        {
             ip=spfa();
             if(ip<0)
                break;
             now[ip]++;
             while(pa[ip]>=0)
             {
                 uk[pa[ip]][ip]=1;
                 uk[ip][pa[ip]]=0;
                 ip=pa[ip];
             }
             now[ip]--;
        }
        for(i=0;i<n;i++)
        {
            dk=deg[i]+now[i];
            tot-=dk*(dk-1)/2;
        }
        printf("%d\n",tot);
        for(i=0;i<n;i++)
        {
           for(j=0;j<n;j++)
           {
               if(mat[i][j]=='2')
                   mat[i][j]=uk[i][j]+'0';
               putchar(mat[i][j]);
               putchar(' ');
           }
           printf("\n");
        }
    }
    return 0;
}

时间复杂度上界是 O(m^2),但是实测结果远远达不到，大概只有 线性，而且 大范围数据仅仅是 输入输出消耗时间