先来%一下Robert Tarjan前辈

%%%%%%%%%%%%%%%%%%

然后是热情感谢下列并不止这些大佬的博客：

图连通性（一）：Tarjan算法求解有向图强连通分量

图连通性（二）：Tarjan算法求解割点/桥/双连通分量/LCA

初探tarjan算法（求强连通分量）

关于Tarjan算法求点双连通分量

图的割点、桥与双连通分支

感谢有各位大佬的博客帮助我理解和学习，接下来就是进入正题。

关于tarjan，之前我写过一个是求lca的随笔，而找lca只是它一个小小的功能，它还有很多其他功能，具体是什么，我就根据自己的学习进程，一步步来自我回忆一下。

第一个是有向图求强连通分量。

让我们来引进百度

有向图强连通分量:在有向图G中，如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

通俗解释，强连通就是有向图中，任意两个顶点彼此有一条路可以可以走到，而强连通分量就是它的强连通子图，极大强连通分量就是它最大的那个强连通子图。 而详细步骤的话，上面的博客已经讲得很清楚了，我就简单的阐述一下步骤。 首先便是遍历没被访问过的点，然后对它进行访问，dfn就代表着一个访问时间戳，类似dfs序，然后low其实就是从这个点能够走到的点的最小的时间戳。 对于每个点u，我们把它压入栈中，然后去访问它能够走到的点v，同时更新它的low值，这里的话，如果是u->v树枝边，用low[v]更新，u->v是后向边并且v在栈中的话，用dfn[v]更新。 因为遍历的时候，类似树的遍历，u->v为树枝边的话，类似v在u的子树里。u->v是后向边的话，类似v是u的祖先或者是被u子树里其他点遍历过的，如果不在栈中的话，说明v是其他强连通分量的了，就不能再用它来更新u。 当tarjan回溯到u这个节点时，如果dfn[u]==low[u]，则说明存在一个强连通分量，就把栈中点一直弹出一直到点u，这些点就属于同一个强连通分量。 因为dfn[u]==low[u]的话，说明u走回不到它的祖先，而栈顶一直到u的点，是u能走到的点，而回溯到u，它们还在栈中，说明它们也能走到u,所以这些都是彼此可达的点，也就是一个强连通分量。 然后强连通分量缩点的话，就是把在同一强通分量的点染色。 接下来直接做些题来找一找感觉吧。

迷宫城堡

HDU - 1269题意：问任意两个房间是不是连通的。 就直接求强连通分量是不是只有一个。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=1e4+11,M=1e5+11; 5 struct Side{ 6int v,ne; 7 }S[M]; 8 bool ins[N],in[N],out[N]; 9 int n,sn,dn,tn,head[N],dfn[N],low[N],sta[N];10 int cn,col[N];11 void init(){12sn=dn=tn=cn=0;13for(int i=0;i<=n;i++){14 head[i]=-1;15 dfn[i]=0;16}17 }18 void add(int u,int v){19S[sn].v=v;20S[sn].ne=head[u];21head[u]=sn++;22 }23 void tarjan(int u){24ins[u]=true;25sta[++tn]=u;26dfn[u]=low[u]=++dn;27for(int i=head[u],v;~i;i=S[i].ne){28 v=S[i].v;29 if(!dfn[v]){30 tarjan(v);31 low[u]=min(low[u],low[v]);32 }else if(ins[v]) low[u]=min(low[u],dfn[v]);33}34if(dfn[u]==low[u]){35 col[u]=++cn;36 ins[u]=false;37 while(sta[tn]!=u){38 col[sta[tn]]=cn;39 ins[sta[tn--]]=false;40 }41 tn--;42}43 }44 int main(){45int m,u,v;46while(scanf("%d%d",&n,&m)&&(n||m)){47 init();48 while(m--){49 scanf("%d%d",&u,&v);50 add(u,v);51 }52 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);53 if(cn==1) puts("Yes");54 else puts("No");55}56return 0;57 }

迷宫

P2863牛的舞会The Cow Prom

题意：两只牛通过绳子连起来，一个牛能不能跳圆舞就是看顺着绳子的方向，能不能回到它。一只牛是跳不了圆舞的，问能跳圆舞的牛的组合有多少组。

就求点数大于的强连通分量个数。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=1e4+118,M=5e4+118; 5 struct Side{ 6int v,ne; 7 }S[M]; 8 bool ins[N]; 9 int sn,dn,tn,ans,head[N],dfn[N],low[N],sta[N];10 void init(int n){11sn=dn=tn=ans=0;12sta[0]=-1;13for(int i=0;i<=n;i++){14 dfn[i]=0;15 head[i]=-1;16}17 }18 void add(int u,int v){19S[sn].v=v;20S[sn].ne=head[u];21head[u]=sn++;22 }23 void tarjan(int u){24ins[u]=true;25sta[++tn]=u; 26dfn[u]=low[u]=++dn;27for(int i=head[u],v;~i;i=S[i].ne){28 v=S[i].v;29 if(!dfn[v]){30 tarjan(v);31 low[u]=min(low[u],low[v]);32 }else if(ins[v]) low[u]=min(low[u],dfn[v]);33}34if(dfn[u]==low[u]){35 int num=1;36 ins[u]=false;37 while(sta[tn]!=u){38 num++;39 ins[sta[tn--]]=false;40 }41 if(num>1) ans++;42 tn--;43}44 }45 int main(){46int n,m,u,v;47while(~scanf("%d%d",&n,&m)){48 init(n);49 for(int i=0;i<m;i++){50 scanf("%d%d",&u,&v);51 add(u,v);52 }53 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);54 printf("%d\n",ans);55}56return 0;57 }

牛牛牛

P1726 上白泽慧音

题意：求最大的强连通分量，多个的话输出字典序最小的。

一个节点只会属于一个连通块，直接记录强连通记录和最小的节点编号，然后把同一个强连通的节点染色一下，由小到大把属于答案那个强连通分量的节点编号输出。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=5e3+11,M=5e4+11; 5 struct Side{ 6int v,ne; 7 }S[M<<1]; 8 bool ins[N]; 9 int n,sn,tn,dn,head[N],dfn[N],low[N],sta[N];10 int cn,ansc,col[N],size[N],minc[N];11 void init(){12sn=dn=tn=cn=0;13ansc=0;14for(int i=0;i<=n;i++){15 dfn[i]=0;16 size[i]=0;17 minc[i]=n+1;18 head[i]=-1;19}20 }21 void add(int u,int v){22S[sn].v=v;23S[sn].ne=head[u];24head[u]=sn++;25 }26 void tarjan(int u){27ins[u]=true;28sta[++tn]=u;29dfn[u]=low[u]=++dn;30for(int i=head[u],v;~i;i=S[i].ne){31 v=S[i].v;32 if(!dfn[v]){33 tarjan(v);34 low[u]=min(low[u],low[v]);35 }else if(ins[v]) low[u]=min(low[u],dfn[v]);36}37if(dfn[u]==low[u]){38 col[u]=++cn;39 ins[u]=false;40 size[cn]=1;41 minc[cn]=u;42 while(sta[tn]!=u){43 col[sta[tn]]=cn;44 size[cn]++;45 minc[cn]=min(minc[cn],sta[tn]);46 ins[sta[tn--]]=false;47 }48 if(size[cn]>size[ansc]||(size[cn]==size[ansc]&&minc[cn]<minc[ansc])) ansc=cn;49 tn--;50}51 }52 int main(){53int m,u,v,op;54while(~scanf("%d%d",&n,&m)){55 init();56 while(m--){57 scanf("%d%d%d",&u,&v,&op);58 add(u,v);59 if(op==2) add(v,u);60 }61 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);62 printf("%d\n",size[ansc]);63 int kg=0;64 for(int i=1;i<=n;i++) if(col[i]==ansc){65 if(kg) printf(" ");66 kg=1;67 printf("%d",i);68 }69 printf("\n");70}71return 0;72 }

上白泽？？

Proving EquivalencesHDU - 2767

题意：a公式能推导b，b能推导c，c能推导a，说明3个等式的等价的，给出n个公式,和m个推导关系，问最少加多少个推导，使得属于公式等价。

其实就是要最少加多少条边使得整个图是强连通的，原图中是有环的，所以我们就用tarjan先把强连通缩点，然后的话，就是一个有向无环图了，那怎么使得我们要使得这个图是强连通的话，其实就是看入度为0和出度为0的点

因为要能到其他点和能被其他点到达，所以肯定要有出有入，那就是出度为0的可以向入度为0的点连一条边，剩下的可以任意连或者自环，答案也就是出度和入度为0的点中，点数更多的那个，还有就是只有一个点的是0，不是1.。。。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=2e4+11,M=5e4+11; 5 struct Side{ 6int v,ne; 7 }S[M]; 8 bool ins[N],in[N],out[N]; 9 int n,sn,dn,tn,head[N],dfn[N],low[N],sta[N];10 int cn,col[N];11 void init(){12sn=dn=tn=cn=0;13for(int i=0;i<=n;i++){14 head[i]=-1;15 dfn[i]=0;16}17 }18 void add(int u,int v){19S[sn].v=v;20S[sn].ne=head[u];21head[u]=sn++;22 }23 void tarjan(int u){24ins[u]=true;25sta[++tn]=u;26dfn[u]=low[u]=++dn;27for(int i=head[u],v;~i;i=S[i].ne){28 v=S[i].v;29 if(!dfn[v]){30 tarjan(v);31 low[u]=min(low[u],low[v]);32 }else if(ins[v]) low[u]=min(low[u],dfn[v]);33}34if(dfn[u]==low[u]){35 col[u]=++cn;36 ins[u]=false;37 while(sta[tn]!=u){38 col[sta[tn]]=cn;39 ins[sta[tn--]]=false;40 }41 tn--;42}43 }44 int solve(){45if(cn==1) return 0;46for(int i=1;i<=cn;i++) in[i]=out[i]=false;47int ci,cj;48for(int i=1;i<=n;i++){49 ci=col[i];50 for(int j=head[i];~j;j=S[j].ne){51 cj=col[S[j].v];52 if(ci!=cj){53 out[ci]=true;54 in[cj]=true;55 }56 }57}58int noi=0,noo=0;59for(int i=1;i<=cn;i++){60 if(!in[i]) noi++;61 if(!out[i]) noo++;62}63return max(noi,noo);64 }65 int main(){66int t,m,u,v;67scanf("%d",&t);68while(t--){69 scanf("%d%d",&n,&m);70 init();71 while(m--){72 scanf("%d%d",&u,&v);73 add(u,v);74 }75 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);76 printf("%d\n",solve()); 77}78return 0;79 }

公式啊

Summer HolidayHDU - 1827

题意：听说lcy帮大家预定了新马泰7日游，Wiskey真是高兴的夜不能寐啊，他想着得快点把这消息告诉大家，虽然他手上有所有人的联系方式，但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式，这样他可以通知其他人，再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人，至少得花多少电话费就能让所有人都被通知到吗？

就先把强连通缩点，这个点的贡献就是整个强连通里权值最小的那个，然后的话就是看入度为0的点的贡献，因为他们没有人通知，肯定只能由wis通知。

1 //把每个环缩点，统计每个环的最小贡献 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 const int N=1e3+11,M=2e3+11; 6 struct Side{ 7int v,ne; 8 }S[M]; 9 bool ins[N],in[N];10 int n,sn,dn,tn,head[N],dfn[N],low[N],sta[N];11 int cn,col[N],minc[N],cost[N];12 void init(){13sn=dn=tn=cn=0;14for(int i=0;i<=n;i++){15 head[i]=-1;16 dfn[i]=0;17}18 }19 void add(int u,int v){20S[sn].v=v;21S[sn].ne=head[u];22head[u]=sn++;23 }24 void tarjan(int u){25ins[u]=true;26sta[++tn]=u;27dfn[u]=low[u]=++dn;28for(int i=head[u],v;~i;i=S[i].ne){29 v=S[i].v;30 if(!dfn[v]){31 tarjan(v);32 low[u]=min(low[u],low[v]);33 }else if(ins[v]) low[u]=min(low[u],dfn[v]);34}35if(dfn[u]==low[u]){36 col[u]=++cn;37 ins[u]=false;38 minc[cn]=cost[u];39 while(sta[tn]!=u){40 col[sta[tn]]=cn;41 minc[cn]=min(minc[cn],cost[sta[tn]]);42 ins[sta[tn--]]=false;43 }44 tn--;45}46 }47 void solve(){48for(int i=1;i<=cn;i++) in[i]=false;49int ci,cj;50for(int i=1;i<=n;i++){51 ci=col[i];52 for(int j=head[i];~j;j=S[j].ne){53 cj=col[S[j].v];54 if(ci!=cj) in[cj]=true;55 }56}57int ans1=0,ans2=0;58for(int i=1;i<=cn;i++) if(!in[i]) ans1++,ans2+=minc[i];59printf("%d %d\n",ans1,ans2); 60 } 61 int main(){62int m,u,v;63while(~scanf("%d%d",&n,&m)){64 init();65 for(int i=1;i<=n;i++) scanf("%d",&cost[i]);66 while(m--){67 scanf("%d%d",&u,&v);68 add(u,v);69 }70 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);71 solve();72}73return 0;74 }

我也想罗马游

Intelligence SystemHDU - 3072

题意：要把一个情报通知给所有人，彼此能通知到的人属于同一分支，一个人通知跟他同一分支的人不需要花费,否则就有一个花费，求通知所有人的最小花费。

也先强连通缩点，然后的话就是更新一下通知到这个点的最小花费。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=5e4+11,M=1e5+11,inf=1e9+7; 5 struct Side{ 6int v,ne,w; 7 }S[M]; 8 bool ins[N]; 9 int n,sn,dn,tn,head[N],dfn[N],low[N],sta[N];10 int cn,col[N],minc[N];11 void init(){12sn=dn=tn=cn=0;13for(int i=0;i<=n;i++){14 head[i]=-1;15 dfn[i]=0;16}17 }18 void add(int u,int v,int w){19S[sn].w=w;20S[sn].v=v;21S[sn].ne=head[u];22head[u]=sn++;23 }24 void tarjan(int u){25ins[u]=true;26sta[++tn]=u;27dfn[u]=low[u]=++dn;28for(int i=head[u],v;~i;i=S[i].ne){29 v=S[i].v;30 if(!dfn[v]){31 tarjan(v);32 low[u]=min(low[u],low[v]);33 }else if(ins[v]) low[u]=min(low[u],dfn[v]);34}35if(dfn[u]==low[u]){36 col[u]=++cn;37 ins[u]=false;38 while(sta[tn]!=u){39 col[sta[tn]]=cn;40 ins[sta[tn--]]=false;41 }42 tn--;43}44 }45 void solve(){46for(int i=1;i<=cn;i++) minc[i]=inf;47int ci,cj;48for(int i=0;i<n;i++){49 ci=col[i];50 for(int j=head[i];~j;j=S[j].ne){51 cj=col[S[j].v];52 if(ci!=cj) minc[cj]=min(minc[cj],S[j].w);53 }54}55long long ans=0;56for(int i=1;i<=cn;i++) if(minc[i]!=inf) ans+=minc[i];57printf("%lld\n",ans); 58 }59 int main(){60int m,u,v,w;61while(~scanf("%d%d",&n,&m)){62 init();63 while(m--){64 scanf("%d%d%d",&u,&v,&w);65 add(u,v,w);66 }67 for(int i=0;i<n;i++) if(!dfn[i]) tarjan(i);68 solve();69}70return 0;71 }

人传人二毛五

P3387 【模板】缩点

题意：给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

先缩点，然后重新建图就是一个有向无环图了，找到入度为0的点，由它开始dp每个点，更新走到这个点的最大权值，然后最后取一下答案最大值

1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 const int N=1e4+11,M=1e5+11; 6 struct Side{ 7int v,ne; 8 }S[M]; 9 bool ins[N];10 int n,sn,dn,tn,head[N],dfn[N],low[N],sta[N];11 int cn,col[N],val[N],ww[N],in[N],dp[N];12 vector<int> vv[N];13 void init(){14sn=dn=tn=cn=0;15for(int i=0;i<=n;i++){16 dfn[i]=0;17 val[i]=0;18 head[i]=-1;19}20 }21 void add(int u,int v){22S[sn].v=v;23S[sn].ne=head[u];24head[u]=sn++;25 }26 void tarjan(int u){27ins[u]=true;28sta[++tn]=u;29dfn[u]=low[u]=++dn;30for(int i=head[u],v;~i;i=S[i].ne){31 v=S[i].v;32 if(!dfn[v]){33 tarjan(v);34 low[u]=min(low[u],low[v]);35 }else if(ins[v]) low[u]=min(low[u],dfn[v]);36}37if(dfn[u]==low[u]){38 col[u]=++cn;39 val[cn]=ww[u];40 ins[u]=false;41 while(sta[tn]!=u){42 col[sta[tn]]=cn;43 val[cn]+=ww[sta[tn]];44 ins[sta[tn--]]=false;45 }46 tn--;47}48 }49 void dfs(int u){50int v,usize=vv[u].size(); 51for(int i=0;i<usize;i++){52 v=vv[u][i];53 dp[v]=max(dp[v],dp[u]+val[u]);54 dfs(v);55}56 }57 int solve(){58for(int i=1;i<=cn;i++){59 in[i]=0;60 dp[i]=0;61 vv[i].clear();62}63int cu,cv,ans=0;64for(int i=1;i<=n;i++){65 cu=col[i];66 for(int j=head[i];~j;j=S[j].ne){67 cv=col[S[j].v];68 if(cu!=cv){69 in[cv]++;70 vv[cu].push_back(cv); 71 }72 }73}74for(int i=1;i<=cn;i++) if(!in[i]) dfs(i);75for(int i=1;i<=cn;i++) ans=max(ans,dp[i]+val[i]);76return ans;77 }78 int main(){79int m,u,v;80while(~scanf("%d%d",&n,&m)){81 init();82 for(int i=1;i<=n;i++) scanf("%d",&ww[i]);83 while(m--){84 scanf("%d%d",&u,&v);85 add(u,v);86 }87 for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);88printf("%d\n",solve());89}90return 0;91 }

dpppp

强连通的题找的比较多，所以多弄几题，可以看见板子题就是板子题，套就完事了。

然后就是在无向图中的了，割点，桥，点（边）双连通分量。

直接引用一下上面大佬博客的

1.割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。

2.割点集合：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。

3.点连通度：最小割点集合中的顶点数。

4.割边(桥)：删掉它之后，图必然会分裂为两个或两个以上的子图。

5.割边集合：如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。

6.边连通度：一个图的边连通度的定义为，最小割边集合中的边数。

7.缩点：把没有割边的连通子图缩为一个点，此时满足任意两点之间都有两条路径可达。

注：求块<>求缩点。缩点后变成一棵k个点k-1条割边连接成的树。而割点可以存在于多个块中。

8.双连通分量：分为点双连通和边双连通。它的标准定义为：点连通度大于1的图称为点双连通图，边连通度大于1的图称为边双连通图。通俗地讲，满足任意两点之间，能通过两条或两条以上没有任何重复边的路到达的图称为双连通图。无向图G的极大双连通子图称为双连通分量。

通俗解释就是。。没有啥通俗解释，上面的定义就是相应的意思。

那我们就是来一个个来说一下怎么求，首先说明，tarjan算法求得的东西是各个连通块的东西，所以要是要求的原图的东西的话，还需要判连通来判断一下。

然后我们就先来说一个割点怎么求。

首先跟求强连通分量差不多，我们还是得把没访问的点遍历一遍，然后像树的遍历一样去访问这个点以及它能走到的那些点，去更新low，但不需要把点压入栈中，也就是如果v是u的祖先，直接更新low，不用判断在不在栈里（因为压根没有）

然后当我们遍历完u的下一节点v，回溯到u时，如果low[v]>=dfn[u]的话，不就说明，v没法走到u的祖先。所以把u割去，必定分成多个连通块，所以u就是割点。

不过这里得判断u是不是根节点，也就是用来一开始遍历的那个节点，因为像1->2,2->3,3->1的话，用1来作为根节点，也有low[2]>=dfn[1]，但1不是割点

那根节点是不是割点怎么判断呢，也就是看一下它能访问到的连通块有多少个，如果是大于等于两个的话，那它很明显也是割点了。

我最喜欢的做题实战环节。

P3388 【模板】割点（割顶）

题意：给出一个nn个点，mm条边的无向图，求图的割点。

割点模板题，原图不一定连通，要求的是各个连通块的割点。

1 #include<cstdio> 2 #include<vector> 3 using namespace std; 4 const int N=2e4+11; 5 bool isc[N]; 6 int n,dn,dfn[N],low[N]; 7 vector<int> vv[N]; 8 int ans; 9 void init(int n){10dn=0;11for(int i=0;i<=n;i++){12 dfn[i]=0;13 isc[i]=false;14 vv[i].clear();15}16 }17 void findc(int u,int fa){18dfn[u]=low[u]=++dn;19int v,vvs=vv[u].size(),son=0;20for(int i=0;i<vvs;i++){21 v=vv[u][i];22 if(!dfn[v]){23 if(u==fa) son++;24 findc(v,u);25 low[u]=min(low[u],low[v]);26 if(low[v]>=dfn[u]&&u!=fa) isc[u]=true;27 }else low[u]=min(low[u],dfn[v]);28}29if(u==fa&&son>=2) isc[u]=true;30if(isc[u]) ans++;31 }32 int main(){33int n,m,u,v;34while(~scanf("%d%d",&n,&m)){35 init(n);36 while(m--){37 scanf("%d%d",&u,&v);38 vv[u].push_back(v);39 vv[v].push_back(u); 40 }41 ans=0;42 for(int i=1;i<=n;i++) if(!dfn[i]) findc(i,i);43 printf("%d\n",ans);44 int kg=0;45 for(int i=1;i<=n;i++) if(isc[i]){46 if(kg) printf(" "); 47 kg=1;48 printf("%d",i);49 }50 printf("\n");51}52return 0;53 }

板子呀

SPFPOJ - 1523

题意：如果一个节点如果它不可用了，将阻止至少一对可用节点能够在先前完全连接的网络上进行通信，那么它是SPF,求哪些节点是SPF，并且它故障后留下几个子网。

也是割点模板题，子网其实就是连通块，对于一个割点来说，它割掉之后产生的连通块就是能让它是割点的点个数，因为那些点就代表着它那个连通块。

#include<cstdio>#include<vector>#include<algorithm>using namespace std;const int N=1e3+11;int dn,dfn[N],low[N],cut[N];vector<int> vv[N];void init(int n){dn=0;for(int i=0;i<=1000;i++){cut[i]=0;dfn[i]=0;vv[i].clear();}}void findc(int u,int fa){dfn[u]=low[u]=++dn;int v,son=0,vvs=vv[u].size();for(int i=0;i<vvs;i++){v=vv[u][i];if(!dfn[v]){if(u==fa) son++;findc(v,u);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]) cut[u]++;}else low[u]=min(low[u],dfn[v]);}if(u==fa) cut[u]=son-1;}int main(){int u,v=0,t=1;init(1000);while(~scanf("%d",&u)){if(u){scanf("%d",&v);vv[u].push_back(v);vv[v].push_back(u);}else{if(!v) break;for(int i=1;i<=1000;i++) if(!dfn[i]) findc(i,i);printf("Network #%d\n",t++);int num=0;for(int i=1;i<=1000;i++) if(cut[i]>0){num++;printf(" SPF node %d leaves %d subnets\n",i,cut[i]+1);}if(num==0) printf(" No SPF nodes\n");printf("\n");init(1000);v=0;}}return 0;}

SPF

然后从割点也可以看出桥（割边）怎么求了，其他一样，不同的是后向边的话不是u才更新，然后判断一下low[v]>dfn[u]，这样的话v连u都访问不到，说明u->v割去，必定分成多个连通块，所以u->v就是桥。

但其实这里面还有一个问题，这是建立在没有重边的情况下，有重边的话像1->2 1->2 明显1->2不是割边，但是用上面方法1->2是割边，所以有割边的话需要先进行预处理一下。

但也有不需要预处理的方法，就上面博客有提到，我直接引用一下

我们记录每条边的标号（一条无向边拆成的两条有向边标号相同），记录每个点的父亲到它的边的标号，如果边(u,v)是v的父亲边，就不能用dfn[u]更新low[v]。这样如果遍历完v的所有子节点后，发现low[v]=dfn[v]，说明u的父亲边(u,v)为割边。

这样我们通过记录边的编号就很好判断了重边。

Caocao's BridgesHDU - 4738

题意：人妻操在海上弄了些小岛，彼此用桥连接，周瑜只有一个炸弹，要派人去把一个桥炸了，使得所有小岛分成几个连通块，桥上有守卫，派的人不能少于守卫数，问最少派多少人，或者根本不可能完成任务。

就是找权值最小的桥，但是要的是整个图的，所以如果一开始就不连通的话，就不需要派人了，这个没注意到wrong了几发，然后还有就是如果权值最小的是0，也得派一个人。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=1e3+11,M=1e6+11; 5 struct Side{ 6int v,ne,id; 7 }S[M<<1]; 8 int ans; 9 int n,sn,dn,head[N],dfn[N],low[N],fp[N],fa[N],val[M];10 void init(){11sn=dn=0;12for(int i=0;i<=n;i++){13 fa[i]=i;14 fp[i]=-1;15 dfn[i]=0;16 head[i]=-1;17}18 }19 void add(int u,int v,int id){20S[sn].id=id;21S[sn].v=v;22S[sn].ne=head[u];23head[u]=sn++;24 }25 int find(int x){26return fa[x]==x ? x : fa[x]=find(fa[x]);27 }28 void bing(int x,int y){29int fx=find(x),fy=find(y);30if(fx!=fy) fa[fx]=fy;31 }32 void findq(int u){33dfn[u]=low[u]=++dn;34int v,id;35for(int i=head[u];~i;i=S[i].ne){36 v=S[i].v;37 id=S[i].id;38 if(!dfn[v]){39 fp[v]=id;40 findq(v);41 low[u]=min(low[u],low[v]);42 }else if(id!=fp[u]) low[u]=min(low[u],dfn[v]);43}44if(dfn[u]==low[u]&&fp[u]!=-1){45 if(ans==-1) ans=val[fp[u]];46 else ans=min(ans,val[fp[u]]);47}48 }49 int main(){50int m,u,v,w;51while(~scanf("%d%d",&n,&m)&&(n||m)){52 init();53 while(m--){54 scanf("%d%d%d",&u,&v,&w);55 val[m]=w;56 add(u,v,m);57 add(v,u,m);58 bing(u,v);59 }60 ans=-1;61 int flag=1,beg=0;62 for(int i=1;i<=n;i++) if(fa[i]==i){63 if(beg){64 flag=0;65 break;66 }67 beg=i;68 }69 if(!flag){70 printf("0\n");71 continue;72 }73 findq(beg);74 if(!ans) ans++;75 printf("%d\n",ans);76}77return 0;78 }

浪花淘尽英雄

桥的话直接求的比较少，一般是用在求边双连通上。

求点双连通的话，网上的写法太多了，而且不一致，我最后选择了我认为比较对的写法。

对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。

但其中，DFS(u)<=Low(v)，说明u是一个割点的话，跟上面的求割点的说法冲突了，这里我也是满疑惑的，等着可爱的你们给我解惑。

Knights of the Round TablePOJ - 2942

题意：圆桌会议，每个骑士周围坐着两个骑士，彼此有仇的骑士不能坐在周围，开会的骑士的人数得是大于等于3的奇数，问怎么也开不了会的骑士有几个。

这题嘛，就首先，。。。点开题解。。。我是真没想到怎么是点双连通。

然后看完题解之后，我们领悟了，首先每个骑士周围都坐着两个人，然后是围成一个圈，其实这就是个点双连通，每个骑士彼此可达，所以题目也就是求多少个其实不能出现在双连通的奇圈里。（奇圈就是点数是奇数的圈）

这里是有个结论的，如果一个双连通分量内的某些顶点在一个奇圈中（即双连通分量含有奇圈），那么这个双连通分量的其他顶点也在某个奇圈中证明就不证明了，反正我不会，一句话，记住就好。

然后怎么判断有没有奇圈呢，一个图是二分图当且仅当图中不存在奇圈，所以反过来直接判断这个双连通是不是二分图就好了，判断二分图的话就是染色法。

1 #include<cstdio> 2 #include<vector> 3 #include<stack> 4 #include<algorithm> 5 using namespace std; 6 const int N=1e3+11,M=1e6+11; 7 struct Side{ 8int u,v,ne; 9Side(){} 10Side(int u,int v):u(u),v(v){} 11 }S[M<<1]; 12 bool hate[N][N],book[N],expel[N]; 13 int n,sn,dn,bn,head[N],dfn[N],low[N],col[N],bin[N]; 14 stack<Side> sta; 15 vector<int> bb[N]; 16 void init(){ 17sn=dn=bn=0; 18while(sta.size()) sta.pop(); 19for(int i=0;i<=n;i++){ 20 dfn[i]=0; 21 bin[i]=0; 22 head[i]=-1; 23 expel[i]=true; 24 for(int j=0;j<=n;j++) hate[i][j]=false; 25} 26 }27 void add(int u,int v){ 28S[sn].v=v; 29S[sn].ne=head[u]; 30head[u]=sn++; 31 } 32 bool oddc(int u,int cc){ 33col[u]=cc; 34for(int i=head[u],v;~i;i=S[i].ne){ 35 v=S[i].v; 36 if(!book[v]) continue; 37 if(!col[v]&&oddc(v,-cc)) return true; 38 if(col[v]==cc) return true; 39} 40return false; 41 } 42 void pdc(int u,int fa){ 43dfn[u]=low[u]=++dn; 44for(int i=head[u],v;~i;i=S[i].ne){ 45 v=S[i].v; 46 if(!dfn[v]){ 47 sta.push(Side(u,v)); 48 pdc(v,u); 49 low[u]=min(low[u],low[v]); 50 if(low[v]>=dfn[u]){ 51 bb[++bn].clear(); 52 for(int i=0;i<=n;i++){ 53 col[i]=0; 54 book[i]=false; 55 } 56 while(!sta.empty()){ 57 int su=sta.top().u,sv=sta.top().v; 58 sta.pop(); 59 if(su==u&&sv==v) break; 60 if(bin[su]!=bn){ 61bin[su]=bn; 62book[su]=true; 63bb[bn].push_back(su); 64 } 65 if(bin[sv]!=bn){ 66bin[sv]=bn; 67book[sv]=true; 68bb[bn].push_back(sv); 69 } 70 } 71 if(oddc(u,1)){ 72 int bbs=bb[bn].size(); 73 if(bbs<3) continue; 74 for(int i=0;i<bbs;i++) expel[bb[bn][i]]=false; 75 } 76 } 77 }else if(v!=fa){ 78 low[u]=min(low[u],dfn[v]); 79 if(dfn[u]>dfn[v]) sta.push(Side(u,v)); 80 } 81} 82 } 83 int main(){ 84int m,u,v; 85while(~scanf("%d%d",&n,&m)&&(n||m)){ 86 init(); 87 while(m--){ 88 scanf("%d%d",&u,&v); 89 hate[u][v]=hate[v][u]=true; 90 } 91 for(int i=1;i<=n;i++) 92 for(int j=i+1;j<=n;j++) if(!hate[i][j]){ 93 add(i,j); 94 add(j,i); 95 } 96 for(int i=1;i<=n;i++) if(!dfn[i]) pdc(i,i); 97 int ans=0; 98 for(int i=1;i<=n;i++) if(expel[i]) ans++; 99 printf("%d\n",ans);100}101return 0;102 }

我太难了

然后是一题很恐怖的OI题，这题已经没有OJ可以交了，我也只是把它给出的18组测试数据过了一遍，所以就当增加见识了。

[POI1999]仓库管理员

问题描述

码头仓库是一块N×M个格子的矩形，有的格子是空闲的——没有任何东西，有的格子上已经堆放了沉重的货物——太重了而不再可能被移动。

现在，仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不得跨过沉重的不可移动的货物和箱子。当管理 员站在与箱子相邻的格子上时，他可以做一次推动，把箱子推到另一个相邻的格子。考虑到箱子很重，仓库管理员为了节省体力，想尽量减少推箱子的次数。你能帮 帮他么？

输入文件

输入文件第一行有两个数N，M（1<=N,M<=100），表示仓库是N×M的矩形。以下有N行，每行有M个字符，表示一个格子的状态。

S 表示该格子上放了不可移动的沉重货物。w 表示该格子上没有任何东西M 表示仓库管理员初始的位置P 表示箱子的初始位置K 表示箱子的目标位置

输出文件

输出文件只有一行，一个数，表示仓库管理员最少要推多少次箱子。如果仓库管理员不可能将箱子推到目标位置，那么请输出NIE，表示无解。

样例输入

10 12SSSSSSSSSSSSSwwwwwwwSSSSSwSSSSwwSSSSSwSSSSwwSKSSSwSSSSwwSwSSSwwwwwPwwwwwSSSSSSSwSwSwSSSSSSMwSwwwSSSSSSSSSSSSSSSSSSSSSSSS

样例输出

7

首先一看，正常思路展开是双dfs,dp[i][j][k][l]，就箱子的位置人的位置时的最少推动次数，但因为是推动次数不是步数，所以人的位置可以看成方向，dp[i][j][k]代表箱子在i,j位置，人在箱子k方向的最少推动次数，

然后的话就每次是bfs箱子移动的位置，同时改变人的方向，并然后二层bfs判断人能不能走到那个位置。但是数据是100*100的图，很明显这样做的话，会超时，所以就在于怎么把第二层bfs优化。

我们需要的就是知道人能不能从一个位置走到另一个位置，那我们把每个点和周围能走的点连边的话，如果是这两个点在同一个连通块的话，然后如果箱子不在割点位置，那么人肯定可以在两个位置间走来走去，那如果箱子不在割点位置呢，

很明显，这时候就是看那两个位置是不是在同一个连通块，而割点可以属于多个点双连通，这时候可能是其中一个位置是割点，所以我们还得记录一下相应点双连通那个割点。然后第二层bfs就成了O（1）判断

然后我这里就放5组样例，要全部样例的，可以去那个OJ上注册一下账号，不过这题已经不判了，交了也没有。

1 #include<cstdio> 2 #include<queue> 3 #include<stack> 4 #include<algorithm> 5 using namespace std; 6 const int N=111,NN=N*N,M=NN*8; 7 const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; 8 struct Side{ 9int u,v,ne; 10Side(){} 11Side(int u,int v):u(u),v(v){} 12 }S[M]; 13 struct Node{ 14int x,y,d,ac; 15Node(){} 16Node(int x,int y,int d,int ac):x(x),y(y),d(d),ac(ac){} 17 }; 18 stack<Side> sta; 19 char ss[N][N]; 20 bool isc[NN],vis[N][N]; 21 int n,m,sn,dn,bn,head[NN],dfn[NN],low[NN],bin[NN],bf[NN]; 22 int mx,my,px,py,kx,ky,dp[N][N][4],com[N][N][4][4]; 23 void init(){ 24sn=dn=bn=0; 25while(!sta.empty()) sta.pop(); 26for(int i=0;i<=n;i++) 27 for(int j=0;j<=m;j++){ 28 isc[i*m+j]=false; 29 dfn[i*m+j]=0; 30 head[i*m+j]=-1; 31 vis[i][j]=false; 32 for(int k=0;k<4;k++){ 33 dp[i][j][k]=-1; 34 for(int l=0;l<4;l++) com[i][j][k][l]=-1; 35 } 36 } 37 } 38 void add(int u,int v){ 39S[sn].v=v; 40S[sn].ne=head[u]; 41head[u]=sn++; 42 } 43 bool check(int x,int y){ 44return x>=0&&x<n&&y>=0&&y<m&&ss[x][y]!='S'; 45 } 46 void pdc(int u,int fa){ 47dfn[u]=low[u]=++dn; 48int v,son=0; 49for(int i=head[u];~i;i=S[i].ne){ 50 v=S[i].v; 51 if(!dfn[v]){ 52 if(u==fa) son++; 53 sta.push(Side(u,v)); 54 pdc(v,u); 55 low[u]=min(low[u],low[v]); 56 if(low[v]>=dfn[u]){ 57 if(u!=fa) isc[u]=true; 58 bf[++bn]=u; 59 while(!sta.empty()){ 60 int su=sta.top().u,sv=sta.top().v; 61 sta.pop(); 62 if(su==u&&sv==v) break; 63 if(bin[su]!=bn) bin[su]=bn; 64 if(bin[sv]!=bn) bin[sv]=bn; 65 } 66 } 67 }else if(v!=fa){ 68 low[u]=min(low[u],dfn[v]); 69 if(dfn[u]>dfn[v]) sta.push(Side(u,v)); 70 } 71} 72if(u==fa&&son>=2) isc[u]=true; 73 } 74 void bfs1(){ 75queue<Node> q; 76vis[mx][my]=true; 77q.push(Node(mx,my,0,0)); 78int qx,qy,dx,dy; 79while(!q.empty()){ 80 qx=q.front().x; 81 qy=q.front().y; 82 q.pop(); 83 for(int i=0;i<4;i++){ 84 dx=qx+dir[i][0]; 85 dy=qy+dir[i][1]; 86 if(check(dx,dy)&&!vis[dx][dy]&&ss[dx][dy]!='P'){ 87 vis[dx][dy]=true; 88 q.push(Node(dx,dy,0,0)); 89 } 90 } 91} 92 } 93 bool judge(int x,int y,int d1,int d2){ 94if(!isc[x*m+y]) return 1; 95if(com[x][y][d1][d2]!=-1) return com[x][y][d1][d2]; 96int u=(x+dir[d1][0])*m+(y+dir[d1][1]); 97int v=(x+dir[d2][0])*m+(y+dir[d2][1]); 98return com[x][y][d1][d2]=(bin[u]==bin[v]||bf[bin[u]]==v||bf[bin[v]]==u); 99 }100 void bfs2(){101queue<Node> q;102int qx,qy,dx,dy,qd,qac,ans=-1;103for(int i=0;i<4;i++){104 dx=px+dir[i][0];105 dy=py+dir[i][1];106 if(check(dx,dy)&&vis[dx][dy]){107 dp[px][py][i]=0;108 q.push(Node(px,py,i,0));109 }110}111while(!q.empty()){112 qx=q.front().x;113 qy=q.front().y;114 qd=q.front().d;115 qac=q.front().ac;116 q.pop();117 if(qx==kx&&qy==ky){118 ans=qac;119 break;120 }121 dx=qx-dir[qd][0],dy=qy-dir[qd][1];//箱子走到下一个位置 122 if(check(dx,dy)&&dp[dx][dy][qd]==-1){123 dp[dx][dy][qd]=qac+1;124 q.push(Node(dx,dy,qd,qac+1));125 }126 for(int i=0;i<4;i++){//改变人在箱子的方向 127 if(dp[qx][qy][i]!=-1) continue;128 dx=qx+dir[i][0];129 dy=qy+dir[i][1];130 if(check(dx,dy)&&judge(qx,qy,qd,i)){131 dp[qx][qy][i]=qac;132 q.push(Node(qx,qy,i,qac));133 }134 }135}136if(ans==-1) printf("NIE\n");137else printf("%d\n",ans);138 }139 int main(){140while(~scanf("%d%d",&n,&m)){141 init();142 for(int i=0;i<n;i++){143 scanf("%s",ss[i]);144 for(int j=0;j<m;j++){145 if(ss[i][j]=='M') mx=i,my=j;146 else if(ss[i][j]=='P') px=i,py=j;147 else if(ss[i][j]=='K') kx=i,ky=j;148 else if(ss[i][j]=='S') continue;149 for(int k=2;k<4;k++){//因为右下的还未读入，直接跟左上判断 150 int di=i+dir[k][0],dj=j+dir[k][1];151 if(check(di,dj)){152add(i*m+j,di*m+dj);153add(di*m+dj,i*m+j);154 }155 }156 }157 }158 for(int i=0;i<n;i++)159 for(int j=0;j<m;j++)160 if(!dfn[i*m+j]&&ss[i][j]!='S') pdc(i*m+j,i*m+j);161 bfs1();162 bfs2();163}164return 0;165 }

OI爷太强了

1 输入1 2 49 33 3 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 4 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 5 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 6 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 7 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 8 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 9 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 10 SSSSSSSSSSMwwwwwwwwwwwwwSSSSSSSSS 11 SSSSSSSSSSwwSSSSwSwSSwSwSSSSSSSSS 12 SSSSSSSSSSwSSSSSwSwSSwSwSSSSSSSSS 13 SSSSSSSSSSwSSSSSwSwSSwSwSSSSSSSSS 14 SSSSSSSSSSwSSSSSwSwSSwSwSSSSSSSSS 15 SSSSSSSSSSwSSSSSwSwSSwSwSSSSSSSSS 16 SSSSSSSSSSwSSSSSSSSSSSSSSSSSSSSSS 17 SSSSSSSSSSwSSSSSSSSSSSSSSSSSSSSSS 18 SSSSSSSSSSwSSSSSSSSSSSSSSSSSSSSSS 19 SSSSSSSSSSwSSSSSSSSSSSSSSSSSSSSSS 20 SSSSSSSSSSwSSSSSSSSSSSSSSSSSSSSSS 21 SSSSSSSSSSwSSSSSSSSSSSSSSSSSSSSSS 22 SSSSSSSSSSwSSSSSSSSSSSSSSSSSSSSSS 23 SSSSSSSSSSwSwwwSSSSSSSSSSSSSSSSSS 24 SSSSSSSSSSwSwSwSSSSSSSSSSSSSSSSSS 25 SSSSSSSSSwwSwwPwwwwwwwwSSSSSSSSSS 26 SSSSSSSSSwSSSSwSSSwSSSwSSSSSSSSSS 27 SSSSSSSSSwSSSSwSSSwSSSwSSSSSSSSSS 28 SSSSSSSSSwSSSSwSSSwSSwwSSSSSSSSSS 29 SSSSSSwwSwSSSSwSSSwSwwwSSSSSSSSSS 30 SSSSSSwwwwwwwwwwwwwwwwwSSSSSSSSSS 31 SSSSSSwwSwSSSSwSSSSSSSSSSSSSSSSSS 32 SSSSSSwwSwSSSSwSSSSSSSSSSSSSSSSSS 33 SSSSSSwwSSSSSSwSSSSSSSSSSSSSSSSSS 34 SSSSSSwwSSSSSSwSSSSSSSSSSSSSSSSSS 35 SSSSSSwwSSSSSSwSSSSSSSSSSSSSSSSSS 36 SSSSSSwwSSSSSSwSSSSSSSSSSSSSSSSSS 37 SSSSSSwwSSSSwwwSSSSSSSSSSSSSSSSSS 38 SSSSSSwwSSSSwSwSSSSSSSSSSSSSSSSSS 39 SSSSSSwKSSSSwwwwSSSSSSSSSSSSSSSSS 40 SSSSSSwwwwwwwwwwSSSSSSSSSSSSSSSSS 41 SSSSSSSSSSSSwwwwSSSSSSSSSSSSSSSSS 42 SSSSSSSSSSSSSwwSSSSSSSSSSSSSSSSSS 43 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 44 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 45 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 46 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 47 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 48 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 49 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 50 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 51 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 52 输出1： 53 23 54 55 输入2： 56 100 100 57 SMSwwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 58 SPSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwS 59 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwwS 60 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS 61 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS 62 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS 63 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS 64 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS 65 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS 66 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS 67 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS 68 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS 69 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS 70 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS 71 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS 72 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS 73 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS 74 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS 75 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS 76 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS 77 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS 78 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS 79 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS 80 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS 81 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS 82 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS 83 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS 84 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS 85 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 86 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 87 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 88 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 89 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 90 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 91 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 92 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 93 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 94 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 95 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 96 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 97 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 98 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS 99 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS100 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS101 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS102 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS103 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS104 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS105 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSKSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS106 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS107 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS108 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS109 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS110 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS111 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS112 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS113 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS114 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS115 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS116 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS117 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS118 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS119 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS120 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS121 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS122 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS123 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS124 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS125 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS126 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS127 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS128 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS129 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS130 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS131 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS132 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS133 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS134 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS135 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS136 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS137 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS138 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS139 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS140 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS141 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS142 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS143 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS144 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS145 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS146 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS147 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS148 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS149 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS150 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS151 SwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS152 SwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS153 SwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS154 wwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS155 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS156 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwwSS157 输出2：158 4665159 160 输入3：161 100 100162 SMSwwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS163 SPSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwS164 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwwS165 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS166 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS167 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS168 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS169 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS170 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS171 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS172 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS173 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS174 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS175 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS176 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS177 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS178 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS179 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS180 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS181 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS182 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS183 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS184 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS185 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS186 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS187 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS188 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS189 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS190 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS191 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS192 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS193 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS194 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS195 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS196 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS197 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS198 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS199 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS200 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS201 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS202 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS203 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS204 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS205 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS206 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS207 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS208 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS209 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS210 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSKSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS211 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS212 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS213 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS214 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS215 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS216 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS217 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS218 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS219 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS220 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS221 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS222 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS223 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS224 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS225 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS226 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS227 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS228 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS229 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS230 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS231 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS232 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS233 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS234 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS235 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS236 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS237 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS238 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS239 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS240 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS241 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS242 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS243 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS244 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS245 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS246 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS247 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS248 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS249 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS250 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS251 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS252 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS253 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS254 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS255 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS256 SwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS257 SwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS258 SwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS259 wwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS260 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS261 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwwSS262 输出3：263 NIE264 265 输入4：266 100 100267 SMSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS268 SwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS269 SwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSS270 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS271 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS272 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS273 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS274 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS275 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS276 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS277 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS278 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS279 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS280 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS281 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS282 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS283 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS284 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS285 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS286 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS287 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS288 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS289 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS290 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS291 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS292 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS293 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS294 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS295 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS296 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS297 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS298 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS299 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS300 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS301 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS302 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS303 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS304 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS305 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS306 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS307 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS308 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS309 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS310 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS311 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS312 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS313 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS314 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS315 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS316 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS317 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSKSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS318 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS319 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwPwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS320 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS321 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS322 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS323 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS324 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS325 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS326 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS327 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS328 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS329 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS330 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS331 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS332 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS333 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS334 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS335 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS336 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS337 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS338 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS339 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS340 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS341 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS342 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS343 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS344 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS345 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS346 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS347 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS348 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS349 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS350 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS351 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS352 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS353 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS354 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS355 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS356 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS357 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS358 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS359 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS360 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS361 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS362 SwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS363 SwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS364 SwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSS365 SwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS366 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS367 输出4：368 NIE369 370 输入5：371 100 100372 SMSwwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS373 SPSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwS374 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwwS375 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS376 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS377 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS378 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS379 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS380 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS381 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS382 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS383 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS384 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS385 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS386 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS387 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS388 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS389 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS390 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS391 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS392 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS393 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS394 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS395 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS396 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS397 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS398 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS399 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS400 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS401 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS402 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS403 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS404 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS405 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS406 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS407 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS408 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS409 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS410 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS411 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS412 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS413 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS414 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS415 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS416 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS417 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS418 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS419 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS420 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSKSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS421 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS422 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS423 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS424 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS425 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS426 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS427 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS428 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS429 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS430 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS431 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS432 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS433 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS434 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS435 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS436 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS437 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS438 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS439 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS440 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS441 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS442 SwSwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS443 SwSwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS444 SwSwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSwSS445 SwSwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSwSS446 SwSwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSwSS447 SwSwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSwSS448 SwSwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSwSS449 SwSwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSwSS450 SwSwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSwSS451 SwSwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSwSS452 SwSwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSwSS453 SwSwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSwSS454 SwSwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSwSS455 SwSwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSwSS456 SwSwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSwSS457 SwSwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSwSS458 SwSwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSwSS459 SwSwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSwSS460 SwSwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSwSS461 SwSwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSwSS462 SwSwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSwSS463 SwSwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSwSS464 SwSwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSwSS465 SwSwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSwSS466 SwSwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSwSS467 SwSwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSwSS468 SwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSwSS469 wwSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwSwSS470 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwSS471 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSwwSS472 输入5：473 4843

样例

对于边双连通分支，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支，其余的边和每个顶点都属于且只属于一个边双连通分支。

所以我们只要连把桥找出来，然后再dfs时跳过桥类似染色一样就可以得出边双连通了。

然后一个有桥的连通图，如何把它通过加边变成边双连通图？

统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。

Redundant PathsPOJ - 3177

题意：问需要新建多少条路，然后两点两两连通。

就照着上面的步骤实现就行。

1 //统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。 2 //则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通， 3 //所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最 4 //近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个 5 //点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连 6 //通的。然后再找两个最近公共祖先最远的两个叶节点， 7 //这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。 8 #include<cstdio> 9 #include<algorithm>10 using namespace std;11 const int N=5e3+11,M=1e4+11;12 struct Side{13int v,ne,id;14 }S[M<<1];15 bool isq[M],vis[N];16 int n,m,sn,dn,bn,head[N],dfn[N],low[N],fp[N],bin[N],du[N];17 void init(){18sn=dn=bn=0;19for(int i=0;i<=n;i++){20 vis[i]=false;21 dfn[i]=bin[i]=0;22 fp[i]=head[i]=-1;23}24for(int i=0;i<=m;i++) isq[i]=false; 25 }26 void add(int u,int v,int id){27S[sn].id=id;28S[sn].v=v;29S[sn].ne=head[u];30head[u]=sn++;31 }32 void findq(int u){33dfn[u]=low[u]=++dn;34int v,id;35for(int i=head[u];~i;i=S[i].ne){36 v=S[i].v;id=S[i].id;37 if(!dfn[v]){38 fp[v]=id;39 findq(v);40 low[u]=min(low[u],low[v]);41 }if(id!=fp[u]) low[u]=min(low[u],dfn[v]);42}43if(fp[u]!=-1&dfn[u]==low[u]) isq[fp[u]]=true;44 }45 void dfs(int u){46bin[u]=bn;47vis[u]=true;48for(int i=head[u];~i;i=S[i].ne){49 if(isq[S[i].id]) continue;50 if(!vis[S[i].v]) dfs(S[i].v);51}52 }53 int main(){54int u,v;55while(~scanf("%d%d",&n,&m)){56 init();57 for(int i=0;i<m;i++){58 scanf("%d%d",&u,&v);59 add(u,v,i);60 add(v,u,i);61 }62 for(int i=1;i<=n;i++) if(!dfn[i]) findq(i);63 for(int i=1;i<=n;i++) if(!vis[i]) bn++,dfs(i);64 for(int i=1;i<=bn;i++) du[i]=0;65 int bi,bj,ans=0;66 for(int i=0;i<m;i++)67 for(int j=head[i];~j;j=S[j].ne){68 bi=bin[i],bj=bin[S[j].v];69 if(bi!=bj) du[bi]++;70 }71 for(int i=1;i<=bn;i++) if(du[i]==1) ans++;72 printf("%d\n",(ans+1)/2);73}74return 0;75 }

板子套一套

还有一题一样的题，数据范围不同而已，可以练一练手。

Road ConstructionPOJ - 3352

1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 const int N=1e3+11,M=2e3+11; 6 struct Side{ 7int v,ne,id; 8Side(){} 9Side(int v,int ne):v(v),ne(ne){}10 }S[M<<1];11 bool isq[M],vis[N];12 int n,m,sn,dn,bn,head[N],dfn[N],low[N],fp[N],bin[N],du[N];13 vector<Side> qiao;14 void init(){15sn=dn=bn=0;16qiao.clear();17for(int i=0;i<=n;i++){18 vis[i]=false;19 dfn[i]=bin[i]=0;20 fp[i]=head[i]=-1;21}22for(int i=0;i<=m;i++) isq[i]=false; 23 }24 void add(int u,int v,int id){25S[sn].id=id;26S[sn].v=v;27S[sn].ne=head[u];28head[u]=sn++;29 }30 void findq(int u,int fa){31dfn[u]=low[u]=++dn;32int v,id;33for(int i=head[u];~i;i=S[i].ne){34 v=S[i].v;id=S[i].id;35 if(!dfn[v]){36 fp[v]=id;37 findq(v,u);38 low[u]=min(low[u],low[v]);39 }if(id!=fp[u]) low[u]=min(low[u],dfn[v]);40}41if(fp[u]!=-1&dfn[u]==low[u]){42 isq[fp[u]]=true;43 qiao.push_back(Side(fa,u)); 44}45 }46 void dfs(int u){47bin[u]=bn;48vis[u]=true;49for(int i=head[u];~i;i=S[i].ne){50 if(isq[S[i].id]) continue;51 if(!vis[S[i].v]) dfs(S[i].v);52}53 }54 int main(){55int u,v;56while(~scanf("%d%d",&n,&m)){57 init();58 for(int i=0;i<m;i++){59 scanf("%d%d",&u,&v);60 add(u,v,i);61 add(v,u,i);62 }63 for(int i=1;i<=n;i++) if(!dfn[i]) findq(i,-1);64 for(int i=1;i<=n;i++) if(!vis[i]) bn++,dfs(i);65 for(int i=1;i<=bn;i++) du[i]=0;66 int bu,bv,ans=0,qis=qiao.size();67 printf("%d\n",qis);68 for(int i=0;i<qis;i++){69 bu=bin[qiao[i].v];70 bv=bin[qiao[i].ne];71 du[bu]++;72 du[bv]++;73 }74 for(int i=1;i<=bn;i++) if(du[i]==1) ans++;75 printf("%d\n",(ans+1)/2);76}77return 0;78 }

汤没换，药也没换

NetworkPOJ - 3694

题意：问每次在两点间加一条边，还剩下多少个桥。

我们先求出边双连通，然后缩点把桥加回来的话，就是一棵树了，然后每次在两个点之间加边的话，就是它们到它们最近公共祖先的边，原先是桥的边，现在就不是了。

这个处理可以用树链剖分，很明显的路径修改，不过看了网上还有个就是并查集直接把路径上的点合并的方法。

1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 using namespace std; 5 const int N=1e5+11,M=2e5+11; 6 struct Side{ 7int v,ne,id; 8Side(){} 9Side(int v,int ne):v(v),ne(ne){} 10 }S[M<<1]; 11 bool isq[M],vis[N]; 12 int n,m,sn,bn,dn,head[N],dfn[N],low[N]; 13 int fp[N],bin[N],up[N],dep[N],bf[N]; 14 vector<int> vv[N]; 15 vector<Side> qiao; 16 void init(){ 17sn=bn=dn=0; 18qiao.clear(); 19for(int i=0;i<=n;i++){ 20 vis[i]=false; 21 dfn[i]=bin[i]=0; 22 fp[i]=head[i]=-1; 23} 24for(int i=0;i<=m;i++) isq[i]=false; 25 } 26 void add(int u,int v,int id){ 27S[sn].id=id; 28S[sn].v=v; 29S[sn].ne=head[u]; 30head[u]=sn++; 31 } 32 void findq(int u,int fa){ 33dfn[u]=low[u]=++dn; 34int v,id; 35for(int i=head[u];~i;i=S[i].ne){ 36 v=S[i].v;id=S[i].id; 37 if(!dfn[v]){ 38 fp[v]=id; 39 findq(v,u); 40 low[u]=min(low[u],low[v]); 41 }else if(id!=fp[u]) low[u]=min(low[u],dfn[v]); 42} 43if(fp[u]!=-1&&dfn[u]==low[u]){ 44 isq[fp[u]]=true; 45 qiao.push_back(Side(fa,u)); 46} 47 } 48 void dfs1(int u){ 49vis[u]=true; 50bin[u]=bn; 51for(int i=head[u];~i;i=S[i].ne){ 52 if(isq[S[i].id]) continue; 53 if(!vis[S[i].v]) dfs1(S[i].v); 54} 55 } 56 void dfs2(int u){ 57int v,vvs=vv[u].size(); 58for(int i=0;i<vvs;i++){ 59 v=vv[u][i]; 60 dep[v]=dep[u]+1; 61 up[v]=u; 62 dfs2(v); 63} 64 } 65 int find(int x){ 66return bf[x]==x ? x : bf[x]=find(bf[x]); 67 } 68 void bing(int x,int y){ 69int fx=find(x),fy=find(y); 70if(fx!=fy) bf[fx]=fy; 71 } 72 int lca(int u,int v){ 73int ans=0; 74while(dep[u]>dep[v]){ 75 bing(u,up[u]); 76 ans++; 77 u=find(up[u]); 78} 79while(dep[v]>dep[u]){ 80 bing(v,up[v]); 81 ans++; 82 v=find(up[v]); 83} 84while(u!=v){ 85 bing(u,up[u]); 86 bing(v,up[v]); 87 ans+=2; 88 u=find(up[u]); 89 v=find(up[v]); 90} 91return ans; 92 } 93 int main(){ 94int u,v,q,t=1; 95while(~scanf("%d%d",&n,&m)&&(n||m)){ 96 init(); 97 for(int i=0;i<m;i++){ 98 scanf("%d%d",&u,&v); 99 add(u,v,i);100 add(v,u,i);101 }102 for(int i=1;i<=n;i++) if(!dfn[i]) findq(i,-1);103 for(int i=1;i<=n;i++) if(!vis[i]) bn++,dfs1(i);104 for(int i=1;i<=bn;i++){105 bf[i]=i;106 vv[i].clear();107 }108 int bu,bv,qis=qiao.size();109 for(int i=0;i<qis;i++){110 bu=bin[qiao[i].v];111 bv=bin[qiao[i].ne];112 vv[bu].push_back(bv); 113 }114 dep[1]=1;115 dfs2(1);116 scanf("%d",&q);117 printf("Case %d:\n",t++);118 while(q--){119 scanf("%d%d",&u,&v);120 bu=find(bin[u]);121 bv=find(bin[v]);122 qis-=lca(bu,bv);123 printf("%d\n",qis);124 }125}126return 0;127 }

上树是不可能上树的了

到此，大概就梳理到这些了，接下来主要心思转向数论。还是感觉自己有些松散，不然按照自己打算的计划，一两周前就该把这个完成了，唉，继续前进把，