Description
(Mirko) 和 (Slavko) 喜欢一起去远足。
(Mirko) 偏好攀登山峰，而 (Slavko) 偏爱山谷。因此每次他们登上一座山峰后，(Slavko) 会决定下次去哪个山谷玩（如果存在索道），同理每次游玩一个山谷后，(Mirko) 会决定下次去攀登哪座山峰（如果存在索道）。于是，不会出现连续两次游玩山峰或者连续两次游玩山谷的情况。为了享受更多乐趣，他们不会去已经去过的景点。
如果他们逛完一个景点后，发现接下来无法乘坐索道前往任何可行的景点，那么这次旅行就结束了。这时，如果最终景点是山峰，则 (Mirko) 获胜，否则 (Slavko) 获胜。
假设两个人都足够聪明，请你计算：从任意一座山峰开始旅行，最终谁会获胜？
Input
第一行为两个正整数 (N)、(M)，表示有 (N) 座山峰、(N) 个山谷和 (M) 条索道。
接下来 (M) 行，每行两个正整数 (vi) 、(di) ，表示在第 (vi) 座山峰和第 (di) 个山谷之间存在一条索道。任意一对山峰和山谷之间至多有一条索道。
Output
输出 (N) 行，每行一个字符串。第 (i) 行的字符串表示，假如旅行出发点是第 (i) 座山峰，那么最终谁会获胜。注意区分大小写。
Sample Input
4 5
2 2
1 2
1 1
1 3
4 2
Sample Output
Slavko
Mirko
Mirko
Mirko
HINT
【数据规模与约定】
对于 (30%) 的数据，(1 leq N leq 10) 。
对于额外 (20%) 的数据，任意两个景点之间至多存在一条简单路径，构成一个森林。
对于 (100%) 的数据，(1 leq N, M leq 5000, M leq N ^2)。
来源：(NOI2019) 北京队集训
想法
考试的时候当然没想出来，就写了个50分的暴力（树形 (dp) +状压 (dp)），结果因为数组开小了爆零 QwQ
正解 %%% (hzk) 大神
比较套路，考虑做个二分图的最大匹配。
从某个山峰处出发，若当前没有匹配，且找不到增广路，则 (Mirko) 赢。
为什么呢？因为不管走到哪个山谷点，都可以顺着当前的匹配边走到山峰，直到到某个山峰没有出路。
那么，得出结论：
从某个山峰出发，若这个山峰在某个最大匹配中未被匹配，则 (Mirko) 赢，否则 (Slavko) 赢。
怎么判断呢？
先匈牙利算法跑出一个最大匹配，然后从每个非匹配的山峰点往前找增广路，找的过程中经过的山峰点都可能在某个最大匹配中未被匹配（可以这样理解，当前未匹配的点一次顺着当前找的过程中已经过的边匹配，这个新点就变成了此时的未匹配点）
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 5005;
struct node{
int v;
node *nxt;
}pool[N],*h[N*2];
int cnt;
void addedge(int u,int v){
node *p=&pool[++cnt];
p->v=v;p->nxt=h[u];h[u]=p;
}
int n,m;
int con[N],vis[N];
bool find(int u){
int v;
for(node *p=h[u];p;p=p->nxt){
if(vis[v=p->v-n]) continue;
vis[v]=1;
if(!con[v] || find(con[v])){
con[v]=u;
return true;
}
}
return false;
}
int no[N];
void getno(int u){
int v;
no[u]=1;
for(node *p=h[u];p;p=p->nxt){
if(vis[v=p->v-n]) continue;
vis[v]=1;
getno(con[v]);
}
}
int main()
{
int u,v;
n=read(); m=read();
for(int i=0;i<m;i++) {
u=read(); v=read()+n;
addedge(u,v);
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(find(i)) no[i]=0;
else{
no[i]=1;
memset(vis,0,sizeof(vis));
getno(i);
}
}
for(int i=1;i<=n;i++)
if(no[i]) printf("Mirko
");
else printf("Slavko
");
return 0;
}