HNOI2019 tour的出题人是我。第一天任何一个题都不是我出的，pdf作者写我是一个印刷错误。fish的出题人在这里进行了说明。
（我突然意识到吉司机题面写九条可怜的强大之处了。如果同样的情况发生在他身上，就算pdf出了错一看题面就知道不是他出的）
这个题出了一定的锅，其中我也有一定的责任。我出这个题的时候最开始没有加读入优化，后面加了读入优化意识到标程非常快，于是把$n$开到了5000。我虽然有和命题组的人说我改了数据范围，也发了新的题面，但我并没有强调所以他们可能最后并没有意识到题面的修改(也有可能意识到了但是版本混淆了），所以最后题面还是3000的版本，但是数据却用的是新的。
最后考场上我只好给了3个3000的数据。由于我数据生成器的特殊性，我不太敢保证我能卡掉所有暴力做法或者错误做法（其实我还是比较自信的因为我觉得如果你真有很高端的优化你也差不多会正解了）。
在UOJ上这个题的范围依然是5000，如果你们考场的程序过不去，请把n改成5000。我相信能过3000的程序都能过5000。
下面放简易题解：
30分的DP就是dp[i][j]表示i到j是否存在一条合法的路径，转移就是枚举i的边和j的边。总复杂度是$O(m ^ 2)$。
考虑减少边数。我们把一种标号单独拿出来，只考虑连接同一种标号的两个点的边。 对于一个连通块，如果它是二分图，那么我们仅保留一棵生成树答案也不会变。这是因为我们容易发现这个连通块之内的转移仍然可以实现（只要另一边在两个点内来回走即可）。如果它不是二分图，我们可以加一个自环。
我们考虑连接不同标号的边，只把这些边拿出来我们也可以形成若干个连通块。对于每个连通块， 根据同样的道理我们保留一棵生成树即可（注意这个时候连通块一定都是二分图）。
这样总边数不超过$2n - 2$，用30分DP的思路可以做到$O(n ^ 2)$并且通过本题。
此外，存在一个$O(nm)$的做法能过70分，做法大概就是DP的时候先转移一边再转移另一边。这个做法和正解并没有多大关系而且如果你缩了图之后再用这个做法会比直接dp更慢，所以不再赘述。
吐槽(雾)
"妈妈这个出题人好懒题解写的太简单看不懂怎么办?"
洛谷上有不少其他人写的(很可能更详细好懂的)题解可供参考:
鄂公网安备 42010202000505 号