不妨考虑树的情况，对于图只要取一棵生成树即可。\(k\le4n\)是容易的，两个点分别dfs就是\(\le4n\)次。对于\(k\le3n\)，考虑一个做法：一个人去遍历整棵树，每次拓展新点时交换。不难证明正确性，次数\(\le3n\)。考虑优化这个策略。注意到其中一个点一直在根，这非常浪费。事实上