题目大意：
定义 \("color \,change"\) 表示两条边有一个公共节点，颜色不一样。
给你一张图，Alice 可以给图上的边上色，红色或者是蓝色，Alice 上色完毕之后，Bob可以选择一条路从1开始到n，他可以选择任意一条路，当时要求减少 \("color \,change"\) 的次数，然后 Alice 希望 \("color\,change"\) 的次数尽量大。求Alice 上色之后，Bob 从1 到 n 最少的颜色改变次数。
题解：
最后答案是 1 到 n 的 最短路k - 1，设最短路为 \(k\)
构造：
如果节点 \(x\) 与 1 的距离为 \(d[x]\) ，如果 \(d[x]\) 为偶数，那么 \(d[x]==d[y]+1\) 的 \((x,y)\) 这条边就赋值为 红色，否则这条边赋值为蓝色，其他边没有涉及这种最短路的就可以任意赋值了。
这样构造出来的图，就满足条件，因为最短距离为1，次数是0，最短距离为2的一定是从最短距离1转移过来，所以次数是1，最短距离为3，是从最短距离为2转移，所以次数是2，当然最短距离是3也可以从3转移，但是那个为3的节点次数已经是2了，所以并不影响这个结果，以此类推。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
vector<int>G[maxn];
void add(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
struct node{
int u,d;
node(int u=0,int d=0):u(u),d(d){}
bool operator<(const node&a)const{
return a.d<d;
}
};
priority_queue<node> que;
int d[maxn],vis[maxn];
void dij(){
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
d[1] = 0;
que.push(node(1,0));
while(!que.empty()){
node x = que.top();que.pop();
int u = x.u;
if(vis[u]) continue;
vis[u] = true;
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(d[v]>d[u]+1){
d[v] = d[u] + 1;
que.push(node(v,d[v]));
}
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
dij();
printf("%d\n",d[n] - 1);
}