Time Limit: 1000ms Memory Limit: 128MB
Description
最小点覆盖是指在二分图中，用最小的点集覆盖所有的边。当然，一个二分图的最小点覆盖可能有很多种。
现在给定一个二分图，请你把图中的点分成三个集合：
如果在任何一种最小点覆盖中都不包含这个点，则认为该点属于N集合。
如果在任何一种最小点覆盖中都包含这个点，则认为该点属于A集合。
如果一个点既不属于N集合，又不属于A集合，则认为该点属于E集合。
Input
第一行包含三个整数n, m, k，分别表示二分图A侧点的数量，二分图B侧点的数量，边的数量。
接下来k行，每行两个整数i, j，分别表示二分图A侧第i号点与二分图B侧第j号点有连边。
数据保证无重边。
Output
第一行输出一个长度为n的字符串，其中第i个字符表示二分图A侧第i个点所属的集合。
第二行输出一个长度为m的字符串，其中第i个字符表示二分图B侧第i个点所属的集合。
Sample Input
11 9 22
1 1
1 2
1 3
1 8
1 9
2 1
2 3
3 2
3 4
4 3
4 5
5 2
5 4
5 6
6 6
6 7
7 5
7 7
8 7
9 7
10 7
11 7
Sample Output
AEEEEEENNNN
EEEEEEANN
HINT
对于10%的数据，$1≤n,m≤5$
对于40%的数据，$1≤n,m≤100$
对于100%的数据，$1≤n,m≤1000, 0≤k≤n∗m$
[吐槽]
场上？嗯。。大眼瞪小眼qwq
[题解]
嗯首先码一下最小点覆盖的相关知识
König定理
一个二分图中最大的匹配数=该图中最小点覆盖数
（写得比较长所以就拎出来啦不然对不起自己就是这样哈哈）
http://www.cnblogs.com/yoyoball/p/7632871.html
从链接回到这道题
铺垫什么的。。好像略微有点多不过。。
嗯不管了
然后我们就可以得出一个结论：
如果一个点没有任何一条匹配边连到，那么这个点肯定不在最小点覆盖中
从而与它相连的点必定要在最小点覆盖中（不然这两点之间的连边就不能覆盖到了）
而对于一个必定在最小点覆盖中的点，与它的匹配点必定不在最小点覆盖中
然后就这样顺着遍历同时标记就好啦
对于那些没有被标记到的点，肯定就是属于E的啦
好的于是在漫长的铺垫之后这题终于解决啦ovo
（果然把最小点覆盖的东西拎出来之后清爽了很多哈哈哈）
[一些细节]
首先。。要用long long
其次。。注意边数
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=*;
struct xxx
{
int y,next;
}a[**];
char mark[MAXN];
bool vis[MAXN];
int h[MAXN],match[MAXN];
int n,m,tot,k,ans;
int add(int x,int y);
bool dfs(int x);
int solve();
int work(int x,int op); int main()
{
// freopen("a.in","r",stdin); int x,y;
scanf("%d%d%d",&n,&m,&k);
memset(h,-,sizeof(h));
tot=;
for (int i=;i<=k;++i)
{
scanf("%d%d",&x,&y);
add(x,n+y); add(n+y,x);
}
memset(match,,sizeof(match));
for (int i=;i<=n+m;++i) mark[i]='E';
for (int i=;i<=n;++i)
if (!match[i])
{
memset(vis,false,sizeof(vis));
if (dfs(i)) ++ans;
}
// for (int i=1;i<=n;++i) printf("%d ",match[i]-n);
solve();
for (int i=;i<=n;++i) printf("%c",mark[i]);
printf("\n");
for (int i=n+;i<=n+m;++i) printf("%c",mark[i]);
} int add(int x,int y)
{
a[++tot].y=y; a[tot].next=h[x]; h[x]=tot;
} bool dfs(int x)
{
int u;
for (int i=h[x];i!=-;i=a[i].next)
{
u=a[i].y;
if (vis[u]) continue;
vis[u]=true;
if (!match[u]||dfs(match[u]))
{
match[x]=u;
match[u]=x;
return true;
}
}
return false;
} int solve()
{
for (int i=;i<=n+m;++i)
{
if (!match[i])
mark[i]='N',work(i,);
}
} int work(int x,int op)
{
int u;
if (op==)
{
mark[x]='A';
work(match[x],);
return ;
}
mark[x]='N';
for (int i=h[x];i!=-;i=a[i].next)
{
u=a[i].y;
if (mark[u]=='E') work(u,);
}
}
挫挫滴代码