$n \leq 300000$的完全无向图，每条边有可行和不可行的状态，一开始只有$m \leq 300000$条边是可行的，给出。每次从$x$走到$y$时，所有与$x$相连的边的可行/不可行状态会改变。问从1最少走几步到$n$。
先考虑只走原来有的路，如果走原来有的路能到$n$，那么这可能是一种可行方案。如果要利用边状态的改变来到达$n$，最优地可以找一个距离为2的点，走到他，再回到1，然后一步到$n$，读者自证不难（考虑每一步如果会出现更优的利用原图没有的边来走会发生什么）。也就是说，直接走路程$\leq4$时直接走，否则找个距离2的绕一圈。
如果没有距离2的点，又不能到$t$，那么1所在的连通分量大概是个菊花，但菊花的叶子是有连边的。这时从1走出去再也回不到1，可删之，与1相连的点变成若干连通块。新到那个点叫$x$，如果$x$的连通块里有个距离$x$为2的点，那可以用上面的方法得到5的答案；如果没有，说明这个点与分量里的所有点有连边，那还要递归下去找吗？不必了，如果枚举所有与1相连的点做如此判断，得不到5的答案就无解了。证明可以联系大前提：没有与1距离大于1的点。
1 //#include2 #include 3 #include 4 //#include 5 //#include 6 //#include 7 //#include 8 #include 9 #include 10 using namespace std;11 12 #define LL long long13 int qread()14 {15 char c; int s=0,f=1; while ((c=getchar())<'0' || c>'9') (c=='-') && (f=-1);16 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*f;17 }18 19 //Pay attention to '-' , LL and double of qread!!!!20 21 int n,m;22 #define maxn 30001123 struct Edge{ int to,next;}edge[maxn<<1]; int first[maxn],le=2;24 void in(int x,int y) {Edge &e=edge[le]; e.to=y; e.next=first[x]; first[x]=le++;}25 void insert(int x,int y) { in(x,y); in(y,x);}26 27 int dis[maxn],pre[maxn],ufs[maxn],que[maxn],head,tail,du[maxn],size[maxn];28 int find(int x) { return x==ufs[x]?x:(ufs[x]=find(ufs[x]));}29 void Union(int x,int y) { if ((x=find(x))!=(y=find(y))) ufs[x]=y,size[y]+=size[x];}30 void bfs(int s)31 {32 for (int i=1;i<=n;i++) dis[i]=0x3f3f3f3f,pre[i]=0;33 head=tail=1; que[tail++]=s; dis[s]=0;34 while (head!=tail)35 {36 int x=que[head++];37 for (int i=first[x];i;i=edge[i].next)38 {39 Edge &e=edge[i]; if (e.to==1) continue;40 if (dis[e.to]==0x3f3f3f3f)41 {42 dis[e.to]=dis[x]+1;43 pre[e.to]=x;44 que[tail++]=e.to;45 }46 }47 }48 }49 50 int main()51 {52 n=qread(); m=qread();53 for (int i=1,x,y;i<=m;i++) {x=qread(); y=qread(); insert(x,y);}54 bfs(1);55 if (dis[n]<=4)56 {57 printf("%d\n1 ",dis[n]);58 int ans[10],lans=0;59 for (int i=n;i!=1;i=pre[i]) ans[++lans]=i;60 for (int i=lans;i;i--) printf("%d ",ans[i]);61 return 0;62 }63 for (int i=1;i<=n;i++) if (dis[i]==2)64 {65 printf("4\n1 %d %d 1 %d",pre[i],i,n);66 return 0;67 }68 for (int i=2;i