存在构造数据，可以将链式前向星、vector 等 遍历边的顺序与加边顺序有关的存图方式 卡成 $O(V^2)$。

默认链式前向星先遍历后加入的边，vector 先遍历先加入的边。

Generator（针对链式前向星）。

#include<bits/stdc++.h>
using namespace std;
mt19937 RND(time(0));
int rnd(int l,int r){return RND()%(r-l+1)+l;}
int main(){
//	freopen("1.in","w",stdout);
	int V=1e4,U=V/2,N=V-1;
	printf("%d\n",N);
	auto add=[](int u,int v){printf("%d %d\n",u,v);};
	for(int i=V;i>=U+3;i--) add(i-2,i);
	add(1,U+2);
	for(int i=1;i<=U;i++) add(i,i+1);
	return 0;
}

具体思路就是造一条链使得加入新点的时候这条链总是增广路的一部分。

要将 vector 存图卡成 $O(V^2)$ 只需要将上面输出全部反过来，即

for(int i=U;i>=1;i--) add(i,i+1);
add(1,U+2);
for(int i=U+3;i<=V;i++) add(i-2,i);

实测将输入的边随机打乱还是这个复杂度。