[还没开始][2nd ucup] Run Twice 站选做

这实在是太神秘了，怎么想到凑一场非传统题的。

我怎么连签子题都不会做，生气了/ng。

比赛链接。

F. Mark on a Graph

题意

初始时有一张 个点 条边的随机无向图，随机方式为每一次随机加入一条当前不存在的边。

现在你可以对这个图进行不超过 次调整，每一次调整为删除一条存在的边或加入一条不存在的边。

目标是使得能区分出随机图和调整过的图。

评测方式为首先输入一张图，你需要判断这张图是随机的还是经过你调整的。

如果是随机的，则你还需要输出调整方案，你输出的图在打乱点编号与边顺序之后将会再次输入。

，。

题解

官方题解很神秘，但是存在一个极其简单的做法。

考虑这张图中度数最大和第二大的点，显然这两个点的度数不可能差的特别大。

那么如果差不超过 ，我们就认为他是随机的，调整方式是给度数最大的点多连几条边。

正确性不会分析。

提交记录。