这是蒟蒻的第一篇题解 QwQ，如果有讲得不好的地方敬请谅解，并欢迎大佬在下方评论区提出宝贵的意见。

首先呢，

我们来看看这道题的题意。

这道题要输入用户的名字对，并统计用户的个数。仔细想想，我们会发现如果用朴素做法，会变得很麻烦，所以我们搬出了 stl。去重我们一般使用 map，因为操作图的时候，我们要使用一个序号与名字对应，所以我们在 map 里定义两个类型，string 和 int，其中，又因为我们要进行搜索，所以 string 放在前面用作 key。

map<string,int> name;
map<string,int>::iterator iter; // 操作容器

int ix,it,tot;// tot 是唯一用户的数量，ix，iy 为当前用户唯一 id
for(int i=1;i<=m;++i){  
    cin>>x>>y;// 输入用户名字
    iter=name.find(x);// 查找是否已存在
    if(iter!=name.end())  ix=iter->second; // 操作容器的值不为map的尾巴，说明存在
    else name.insert(pair<string,int>(x,ix=++tot)); //不存在，插入并顺手将当前 id 设为用户数量自增后的结果
    iter=name.find(y);
    if(iter!=name.end())  iy=iter->second;
    else name.insert(pair<string,int>(y,iy=++tot));
}

接下来，我们就要进行图论部分的操作了。
老规矩，因为这道题考查的是图中单点对单点的关系，所以我们就不使用结构体了，转而使用 stl 中的 vector。

先定义一个 vector：vector<int> ship[MAXN<<1];。

注意，由于图是无向的，所以要添加两次，故定义时 MAXN 要乘 2（二进制写法为 <<1）。

然后在上面输入中，加入：

for(int i=1;i<=m;++i){ 
    // 此处省略上方代码
    ship[ix].push_back(iy);
    ship[iy].push_back(ix);
}

图输入后之后，就可以进行操作了，使用循环来对每个用户进行分析。

根据题意，推荐好友双方必须互不为好友，故我们先要标记一下当前循环到的用户 $i$ 与其他用户 $j$ 是否为好友（别忘了先 memset 下喔）。

for(int i=1;i<=tot;++i){
    memset(flag,0,sizeof flag);
    for(int j=0;j<ship[i].size();++j) flag[ship[i][j]]=1;
}

接着，我们来判断用户 $i$ 的推荐好友，如果循环两方 $i$ 和 $j$ 相同或是好友，就跳过。

如果上方条件都不满足，那么就继续判断。

再用一个子循环来判断 $j$ 的好友是不是 $i$ 的好友，如果是，就把 $i$ 和 $j$ 的共同好友数量加 1
找完之后，我们再看看 $i$ 和 $j$ 共同好友的数量是不是当前用户 $i$ 的推荐好友中共同好友数量并列最大的，如果是，把 $i$ 推荐好友数量加 1。如果 $i$ 和 $j$ 的共同好友数量甚至比之前找到的还要大，那么用户 $i$ 的推荐用户就变为了 $j$ 一人。

并且，在这些操作后，我们要把 $i$ 的共同好友数量记下来，故开一个数组 ans（大小也要开到MAXN的两倍喔）。

for(int i=1;i<=tot;++i){
    int suggest_friends=0; // 推荐用户数量
    memset(flag,0,sizeof flag); // 清空一下
    for(int j=0;j<ship[i].size();++j) flag[ship[i][j]]=1; //  标记 i 和 j 好友
    for(int j=1;j<=tot;++j){
        if(i==j) continue; // 同一个人就跳过吧
        if(!flag[j]){ // 不为好友
            int both_friends=0; // 共同好友数量
            for(int k=0;k<ship[j].size();++k){
                if(flag[ship[j][k]]) both_friends++; // 查找 i 和 j 的共同好友
            }
            if(both_friends>ans[i]){ // i 和 j 的共同好友数量甚至比之前找到的还要大
                suggest_friends=1; // i 的推荐用户就变为了 j 一人。
                ans[i]=both_friends;
            }else if(both_friends==ans[i]) suggest_friends++; // 推荐好友数量加 1
        }
    }
    ans[i]=suggest_friends;// 设成最终的推荐用户数量
}

最后，我们把 ans 的第 $i$ 项设成最终的推荐用户数量。
最后的最后，我们循环输入的用户，输出名字和推荐用户数量（感谢出题人没有要求输出的顺序，否则还要麻烦）。

附上完整 AC 代码

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<cstring>

#define il inline

const int MAXN = 5005;

using namespace std;

map<string,int> name;
map<string,int>::iterator iter;  
vector<int> ship[MAXN<<1];
bool flag[MAXN<<1];
int ans[MAXN];

int m;
int main(){
    std::ios::sync_with_stdio(false);
    cin>>m;
    string x,y;
    int ix,iy,tot=0;
    for(int i=1;i<=m;++i){
        cin>>x>>y;
        iter=name.find(x);
        if(iter!=name.end())  ix=iter->second;
        else name.insert(pair<string,int>(x,ix=++tot));
        iter=name.find(y);
        if(iter!=name.end())  iy=iter->second;
        else name.insert(pair<string,int>(y,iy=++tot));
        ship[ix].push_back(iy);
        ship[iy].push_back(ix);
    }
    cout<<tot<<endl;
    for(int i=1;i<=tot;++i){
        int suggest_friends=0;
        memset(flag,0,sizeof flag);
        for(int j=0;j<ship[i].size();++j) flag[ship[i][j]]=1;
        for(int j=1;j<=tot;++j){
            if(i==j) continue;
            if(!flag[j]){
                int both_friends=0;
                for(int k=0;k<ship[j].size();++k){
                    if(flag[ship[j][k]]) both_friends++;
                }
                if(both_friends>ans[i]){
                    suggest_friends=1;
                    ans[i]=both_friends;
                }else if(both_friends==ans[i]) suggest_friends++;
            }
        }
        ans[i]=suggest_friends;
    }
    for(iter=name.begin();iter!=name.end();++iter){
        cout<<iter->first<<" "<<ans[iter->second]<<endl;
    }
}

快读

返回值版

inline int read() {
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

重载版

inline int read(int& ret) {
    ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    ret*=f;
}

int128 快读快写

#include <bits/stdc++.h>
using namespace std;
inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

int main(){
    __int128 a=read();
    __int128 b=read();
    print(a+b);
    return 0;
}

快速幂

typedef long long ll;
ll quick_pow(ll x,ll n,ll m){
	ll res = 1;
	while(n > 0){
		if(n & 1)	res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

欧拉筛

void phi_table(int n,int* phi) {
  for(int i=2;i<=n;i++) phi[i]=0;
  phi[1]=1;
  for(int i=2;i<=n;i++)
    if (!phi[i])
      for (int j=i;j<=n;j+=i) {
        if (!phi[j]) phi[j]=j;
        phi[j] = phi[j]/i*(i-1);
      }
}

并查集

#include<iostream>
#include<cstdio>

using namespace std;
int fa[10001];
int n,m,p;
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
        return fa[x];
    }
    return x;
}
void set(int x,int y){
    fa[find(x)]=find(y);
}

int main(){
    scanf("%d%d",&n,&m);
    int t0,t1,t2;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&t0,&t1,&t2);
        if(t0==1) set(t1,t2);
        else printf(find(t1)==find(t2)?"Y\n":"N\n");
    }
}

Dijkstra

#include<iostream>
#include<cstdio>
#include<queue>
#define il inline
#define MAXN 100000
using namespace std;

int n,m,s;

struct edge
{
    int to,dis,next;
}e[MAXN];

struct node{
    int val;
    int pos;
    bool operator<(const node &x)const{
        return x.val<val;
    }
};

priority_queue<node> q;
int head[MAXN],dis[MAXN];
bool vis[MAXN];
int cnt=0;

il void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    int a,b,c;
    for(int i=1;i<m;++i){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dis[n]=0;
    q.push(node{0,n});
    while(!q.empty()){
        node cur=q.top();
        q.pop();
        int vv=cur.val,pp=cur.pos;
        if(vis[pp]) continue;
        vis[pp]=1;
        for(int i=head[pp];i;i=e[i].next){
            int yy=e[i].to;
            if(dis[yy]>dis[pp]+e[i].dis){
                dis[yy]=dis[pp]+e[i].dis;
                if(!vis[yy]) q.push(node{dis[yy],yy});
            }
        }
    }
    printf("%d",dis[s]);
}

SPFA

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define il inline
#define MAXN 100000
#define INF 1e9
using namespace std;

int dis[MAXN],head[MAXN];
bool vis[MAXN];

int n,m,s,cnt=0;

struct edge
{
    int to,dis,next;
}e[MAXN];

il void spfa(){
    memset(dis,INF,sizeof dis);
    memset(vis,1,sizeof vis);
    dis[n]=0;
    vis[n]=false;
    queue <int> q;
    q.push(n);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=true;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[u]+e[i].dis<dis[v]){
                dis[v]=dis[u]+e[i].dis;
                if(vis[v]){
                    q.push(v);
                    vis[v]=false;
                }
            }
        }
    }
}

il void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].dis=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    int a,b,c;
    for(int i=1;i<m;++i){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    spfa();
    printf("%d",dis[s]);
}

Kruskal

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

int N,M;
struct edge{
    int u,v,w;
}e[1000001];

int fa[1000001];
int ans,eu,ev,cnt=0;
// cnt=>边数 ans=>边长度之和 eu=>当前起点 ev=>当前终点
using namespace std;

inline bool cmp(edge a, edge b){
    return a.w<b.w;
}

inline int find(int x){
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

inline void kruskal(){
    sort(e+1,e+1+M,cmp);
    for(int i=1;i<=M;++i){
        eu=find(e[i].u),ev=find(e[i].v);
        if(eu==ev) continue;
        //  两点联通
        ans+=e[i].w;
        fa[ev]=eu;
        ++cnt;
        if(cnt==N-1) break;
    }
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;++i){
        fa[i]=i;
    }
    for(int i=1;i<=M;++i){
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    }
    kruskal();
    printf("%d",ans);
}

LCA

倍增

#include<cstdio>
#include<iostream>
#include<algorithm>
#define il inline
const int MAXN=500005;

using namespace std;

int n,m,s;
struct node{
    int to,next;
}e[MAXN<<1];

int head[MAXN],Log2[MAXN],depth[MAXN],fa[MAXN][22];

int cnt=0;
il void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
il void logc(){
    for(int i=1;i<=n;++i) Log2[i]=Log2[i-1]+(1<<Log2[i-1]==i);
}
il void dfs(int cur,int ff){
    fa[cur][0]=ff;depth[cur]=depth[ff]+1;
    for(int i=1;i<=Log2[depth[cur]];++i){
        fa[cur][i]=fa[fa[cur][i-1]][i-1];
    }
    for(int i=head[cur];i;i=e[i].next){
        if(e[i].to!=ff) dfs(e[i].to,cur);
    }
}
il int lca(int x,int y){
    if(depth[x]<depth[y]) swap(x,y);
    while(depth[x]>depth[y]){
        x=fa[x][Log2[depth[x]-depth[y]-1]];
    }
    if(x==y){
        return y;
    }
    for(int k=Log2[depth[x]]-1;k>=0;--k){
        if(fa[x][k]!=fa[y][k]){
            x=fa[x][k],y=fa[y][k];
        }
    }
    return fa[x][0];
}
int main(){
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    logc();
    dfs(s,0);
    int x,y;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
}

tarjan

#include<iostream>
#include<cstdio>
#define il inline
using namespace std;

int n,m,s,x,y,tot=0,vtot=0;
const int N=500005,M=1000005;
int head[N],to[M],nxt[M];
int vhead[N],vto[M],vnxt[M];
int fa[N],lca[2*M];
bool visit[N];
il void add(int x,int y){
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
il void vadd(int x,int y){
    vto[++vtot]=y;
    vnxt[vtot]=vhead[x];
    vhead[x]=vtot;
}
il int find(int u){
    return fa[u]==u?u:fa[u]=find(fa[u]);
}
il void Tarjan(int u){
    visit[u]=true;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(visit[v]) continue;
        Tarjan(v);
        fa[v]=u;
    }
    for(int i=vhead[u];i;i=vnxt[i]){
        int v=vto[i];
        if(visit[v]){
            lca[i]=find(v);
            if(i%2) lca[i+1]=lca[i];
            else lca[i-1]=lca[i];
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        vadd(x,y);vadd(y,x);
    }
    Tarjan(s);
    for(int i=1;i<=m;i++) printf("%d",lca[i*2]);
}

线段树

#include<iostream>
#include<cstdio>
#define il inline
#define ll long long
using namespace std;

ll n,m;

ll a[1000005];
ll ans[1000005];
ll tag[1000005];
il ll leftson(ll x){
    return x<<1;
}
il ll rightson(ll x){
    return x<<1|1;
}
il void dd(ll p,ll l,ll r,ll k){
    ans[p]+=(r-l+1)*k;
    tag[p]+=k;
}
il void pushdown(ll l,ll r,ll p){
    ll mid=(l+r)>>1;
    dd(leftson(p),l,mid,tag[p]);
    dd(rightson(p),mid+1,r,tag[p]);
    tag[p]=0;
}
il void pushup(ll p){
    ans[p]=ans[leftson(p)]+ans[rightson(p)];
}
il void update(ll rl,ll rr,ll l,ll r,ll p,ll k){
    if(rl<=l&&r<=rr){
        ans[p]+=(r-l+1)*k;
        tag[p]+=k;
        return;
    }
    pushdown(l,r,p);
    ll mid=(l+r)>>1;
    if(rl<=mid) update(rl,rr,l,mid,leftson(p),k);
    if(rr>mid) update(rl,rr,mid+1,r,rightson(p),k);
    pushup(p);
}
il void build(ll p,ll l,ll r){
    tag[p]=0;
    if(l==r){ ans[p]=a[l];return; } // 子叶
    ll mid=(l+r)>>1;
    build(leftson(p),l,mid);
    build(rightson(p),mid+1,r);
    pushup(p);
}
il ll query(ll rl,ll rr,ll l,ll r,ll p){
    ll result=0;
    if(rl<=l&&r<=rr){
        return ans[p];
    }
    ll mid=(l+r)>>1;
    pushdown(l,r,p);
    if(rl<=mid) result+=query(rl,rr,l,mid,leftson(p));
    if(rr>mid) result+=query(rl,rr,mid+1,r,rightson(p));
    return result;
}
int main(){
    scanf("%lld%lld",&n,&m);
    ll action,b,c,d;
    for(ll i=1;i<=n;++i) scanf("%lld",a+i);
    build(1,1,n);
    for(ll i=1;i<=m;++i){
        scanf("%lld",&action);
        if(action==1){
            scanf("%lld%lld%lld",&b,&c,&d);
            update(b,c,1,n,1,d);
        }else{
            scanf("%lld%lld",&b,&c);
            printf("%lld\n",query(b,c,1,n,1));
        }
    }
}

拓扑排序

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
 
using namespace std;
 
int n,m;
 
int step=1;
 
void work(vector<vector<int>> &G, vector<int> &indrgee){
    queue<int> q;
    for(int i=1;i<=n;++i)
    if(indrgee[i]==0) q.push(i);
    while(!q.empty()){
        int cur=q.front().first,le=q.front().second;
        q.pop();
        for(int i=0;i<G[cur].size();++i){
            int v=G[cur][i];
	    indrgee[v]--;
	    if (indrgee[v]==0) q.push(v);
        }
        G[cur].clear();
    }
}
 
int main(){
    scanf("%d",&m);
    vector<vector<int>> G(n+1);
    vector<int> indrgee(n);
    int s,t;
    for(int i=1;i<=m;++i){
        scanf("%d",&s,&t);
        G[s].push_back(t);
    }
    for (auto x : G) {
        for (auto y : x) indrgee[y]++;
    }
    work(G, indrgee);
    return 0;
}

介绍

有向无环图

如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图。

拓扑排序

拓扑排序是将有向无环图G的所有顶点排成一个线性序列，使得对图G中的任意两个顶点u、v，如果存在边u->v，那么在序列中u一定在v前面，这个序列又被称为拓扑序列。
如下图：结点0和1没有前驱节点，可以任意访问，但是结点2必须在结点0和1访问完之后才能访问，同理结点3和4必须在结点2访问完以后才能访问，但是结点3和4 之间没有依赖关系，结点5必须在结点3和结点6访问之后才能访问，等等…..因此，对于下图的一个拓扑序列可以是：0,1,2,3,4,6,5,7 也可以是：0,1,2,4,6,3,5,7

拓扑排序步骤如下：

1. 定义一个队列Q，并把所有入度为0的结点加入队列
2. 取队首结点，访问输出，然后删除所有从它出发的边，并令这些边到达的顶点的入度减1，如果某个顶点的入度减为0，则将其加入队列
3. 重复进行 2 操作，直到队列为空。如果队列为空时入过队的结点数恰好为N，说明拓扑排序成功，图G为有向无环图；否则，拓扑排序失败，图G有环

例题

【洛谷】P1083 车站分级

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>

#define MAXN 1005

using namespace std;

// bool vis[MAXN];
int station[MAXN];
bool stop[MAXN];
bool pd[MAXN][MAXN];

int n,m;

int step=1;

void work(vector<vector<int>> &G, vector<int> &indrgee){
    queue<pair<int,int>> q;
    for(int i=1;i<=n;++i)
    if(indrgee[i]==0) q.push(make_pair(i,1));
    while(!q.empty()){
        int cur=q.front().first,le=q.front().second;
        q.pop();
        for(int i=0;i<G[cur].size();++i){
            int v=G[cur][i];
			indrgee[v]--;
			if (indrgee[v]==0){ 
                q.push(make_pair(v,le+1));
                step=max(step,le+1);
            }
        }
        G[cur].clear();
    }
}

int main(){
    scanf("%d%d",&n,&m);
    vector<vector<int>> G(n+1);
    vector<int> indrgee(n);
    int s;
    for(int i=1;i<=m;++i){
        scanf("%d",&s);
        memset(stop,0,sizeof(stop));
        for(int j=1;j<=s;++j){
            scanf("%d",&station[j]);
            stop[station[j]]=1;
        }
        for(int j=station[1];j<=station[s];++j){
            if(stop[j]) continue;
            for(int k=1;k<=s;++k){
                 if(!pd[j][station[k]]){
                     indrgee[station[k]]++;
                     G[j].push_back(station[k]);
                     pd[j][station[k]]=1;
                 }
            }
        }
    }
    // for (auto x:G) {
	// 	for (auto y:x){
    //         if(vis[y]==1) continue;
    //         indrgee[y]++;
    //         vis[y]=1;
    //     }
	// }
    work(G, indrgee);
    printf("%d\n",step);
    return 0;
}

问题模型1-1： 如果在一张图上（有向图和无向图），边权只可能是1或0，现在我们想从某个节点（假设为s）到另一个节点（假设为t），>怎样才能使得路径上的权值和最大？

这是最短路径问题中的特例，因为其边权只可能是0或1；同时这也是许多问题的抽象形式，很多问题可以抽象为上述模型1-1。我们的目标就是找到一个尽可能高效的算法解决上述问题模型。

最短路径算法

这是很容易想到的图论算法，解决此题的效率为O(NM)或O(M log N)，取决于不同的算法。

双端队列BFS

算法描述：

由于这是一张边权要么为0、要么为1的图。在这样的图上，我们可以通过双端队列广搜来计算。算法的整体框架与一般的广搜类似，只是在每个节点沿分支拓展时稍作改变。如果这条分支边权为0，则从队首入队，否则从队尾入队。这样我们能保证，任意时刻广搜队列中节点对应的距离值都有“两端性”和“单调性”，每个节点第一次被访问时，就能得到从左上角到该节点的最短距离。

效率分析：

我们可以知道该算法中每个节点仅被访问一次，因为这是BFS的特性，所以该算法的效率为O(N)。

正确性证明：

由于我们最终目标是求路径权值和，而权值为0的边无论走多少条权值和依旧是+0，因此我们可以优先走权值为0的边，更新与这些边相连的点x的d[x]（d[i] 为从s到i最小权值和），此时d[x]一定是最小的，因为它是由尽可能多的权值为0的边更新而来。所以在队列中取出的节点同时满足“连通性”和“权值最小”，因此每个节点仅需被更新一次。

解题思路：

首先将其转化为一张边权仅由0、1构成的无向图，由于最多可能有500* 500 = 250000个点，1000，000条边，所以用此种方法时需要注意数据范围是否合适。然后就采用双端队列BFS求解，效率为O(N)，在此题中是O(R* C)。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 400000;
const int M = 300000*4;
int head[MAXN],ver[M],Next[M],edge[M],d[MAXN];
bool vis[MAXN];
int tot,r,c,n,m;
void addEdge(int x,int y,int z){
    ver[++tot] = y,edge[tot] = z;
    Next[tot] = head[x],head[x] = tot;
}
void solve(){
    memset(d,0x3f,sizeof d);
    memset(vis,false,sizeof vis);
    d[1] = 0;
    deque<int> q;
    q.push_back(1);
    while(q.size()){
        int x = q.front();q.pop_front();
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i;i = Next[i]){
            int y = ver[i],z = edge[i];
            d[y] = min(d[x] + z,d[y]);
            if(z) q.push_back(y);
            else q.push_front(y);
            //printf("%d %d\n",y,d[y]);
        }
    }
}
void init(){
    memset(head,0,sizeof head);
    memset(Next,0,sizeof Next);
    memset(ver,0,sizeof ver);
    tot = 0;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d%d",&n,&m);
        r = m+1,c = n+1;
        char str[MAXN];
        for(int i = 0;i < n;i++){
            scanf("%s",str);
            for(int j = 1;j <= m;j++){
                if(str[j-1] == '\\'){
                    addEdge(i*r+j,(i+1)*r+j+1,0),addEdge((i+1)*r+j+1,i*r+j,0);
                    addEdge((i+1)*r+j,i*r+j+1,1),addEdge(i*r+j+1,(i+1)*r+j,1);
                }else{
                    addEdge(i*r+j,(i+1)*r+j+1,1),addEdge((i+1)*r+j+1,i*r+j,1);
                    addEdge((i+1)*r+j,i*r+j+1,0),addEdge(i*r+j+1,(i+1)*r+j,0);
                }
            }
        }
        if((n+m)%2) puts("NO SOLUTION");
        else{
            solve();
            printf("%d\n",d[r*c]);
        }
    }
    return 0;
}