HD解

大范围贪心 + 小范围暴力bfs

为了方便，根据对称轴翻转，使得 \((r_1,c_1)\) 出现在 \((r_2,c_2)\) 的左下角

其后再根据点 \((r_1,c_1)\) 位于那一块区域内进行分类讨论

如果点位于上图区域 \(1\) 内，贪心可知刚开始每次都走 \((+2,+1)\) 最优，直到 \(c1=c2\) 时，再反复 \((+2,-1),(+2,+1)\) 向右走，如下图所示：

如果点位于上图区域 \(4\) 内，贪心可知刚开始每次都走 \((+1,+2)\) 最优，直到 \(r1=r2\) 时，再反复 \((-1,+2),(+1,+2)\) 向上走，如下图所示：

如果位于上图区域 \(2\) 内，可以发现先走 \((+1,+2)\)，直到与 \(y=\frac12x\) 这条直线接触时再一直走 \((+2,+1)\) 最优，但这样的走法可能比较难处理？

这种走法实际上与先接触 \(y=x\) 这条直线，再反复 \((+1,+2),(+2,+1)\) 所需要的步数是相同的，也好写OvO

区域 \(3\) 内也是相同，先靠近 \(y=x\) 再向右上走，如下图所示：

当然，以上也只是大范围贪心，小范围内这种走法可能会出问题

因此，最终快要接近终点的时候，限制一下不要直接取到最近的位置，稍微留出个 \(20\times 20\) 大小的位置来跑 EZ 版本的代码即可

int d[35][35];
const int ddx[8]={-2,-2,-1,-1,1,1,2,2};
const int ddy[8]={-1,1,-2,2,-2,2,-1,1};

int solve2(int n,int r1,int c1,int r2,int c2)
{
    mst(d,INF);
    d[r1][c1]=0;
    queue q;
    q.push(pii(r1,c1));
    while(!q.empty())
    {
        pii p=q.front();
        q.pop();
        repp(i,0,8)
        {
            int px=ddx[i]+p.first;
            int py=ddy[i]+p.second;
            if(px>0&&py>0&&px<=n&&py<=n&&d[px][py]>d[p.first][p.second]+1)
            {
                d[px][py]=d[p.first][p.second]+1;
                q.push(pii(px,py));
            }
        }
    }
    return d[r2][c2];
}

void solve()
{
    ll n,r1,c1,r2,c2;
    cin>>n>>r1>>c1>>r2>>c2;
    
    // 如果范围较小，直接调用EZ Ver.的解法
    if(n<=20)
    {
        cout<r2)
    {
        r1=n-r1+1;
        r2=n-r2+1;
    }
    if(c1>c2)
    {
        c1=n-c1+1;
        c2=n-c2+1;
    }
    
    ll ans=0;
    if(r2-r1>c2-c1) //如果x方向的增量比y方向的增量多，位于上图区域3,4
    {
        if(r1+(c2-c1)*2<=r2) //上图区域4
        {
            // 先 (+1,+2) 走到 c1=c2 的位置
            ll d=c2-c1;
            ans+=d;
            r1+=d*2;
            c1=c2;
            // 再反复向上，每两步可以使 y+4
            d=(r2-r1)/4-1; // 注意这里的 -1，为后面的暴力留出空间，下同
            if(d>0)
            {
                ans+=d*2;
                r1+=d*4;
            }
        }
        else //上图区域3
        {
            ll d=(r2-r1)-(c2-c1);
            ans+=d;
            r1+=d*2;
            c1+=d;
            
            d=min(r2-r1,c2-c1)/3-1;
            if(d>0)
            {
                ans+=d*2;
                r1+=d*3;
                c1+=d*3;
            }
        }
    }
    else
    {
        if(c1+(r2-r1)*2<=c2) //上图区域1
        {
            ll d=r2-r1;
            ans+=d;
            c1+=d*2;
            r1=r2;
            
            d=(c2-c1)/4-1;
            if(d>0)
            {
                ans+=d*2;
                c1+=d*4;
            }
        }
        else //上图区域2
        {
            ll d=(c2-c1)-(r2-r1);
            ans+=d;
            c1+=d*2;
            r1+=d;
            
            d=min(r2-r1,c2-c1)/3-1;
            if(d>0)
            {
                ans+=d*2;
                r1+=d*3;
                c1+=d*3;
            }
        }
    }
    
    // 最后差的一点点就暴力跑，特判边界
    if(r1<=4&&c1<=4) // 左下边界
        ans+=solve2(20,r1,c1,r2,c2);
    else if(r2>=n-3&&c2>=n-3) // 右上边界
        ans+=solve2(20,20-(n-r1),20-(n-c1),20-(n-r2),20-(n-c2));
    else
        ans+=solve2(20,10,10,10+(r2-r1),10+(c2-c1));
    cout<

int n,m;
vector G[50050];
int dep[50050];
bool vis[50050];

int dfs(int u,int fa,int d)
{
    if(vis[u])
        return max(d-dep[u],1);
    dep[u]=d;
    vis[u]=true;
    int r=1;
    for(int &v:G[u])
    {
        if(v==fa)
            continue;
        r=r*dfs(v,u,d+1)%mod;
    }
    return r;
}

void solve()
{
    cin>>n>>m;
    rep(i,1,n)
    {
        G[i].clear();
        dep[i]=0;
        vis[i]=false;
    }
    rep(i,1,m)
    {
        int u,v;
        cin>>u>>v;
        G[u].pb(v);
        G[v].pb(u);
    }
    cout<