今天，在经济飞速发展的K国召开了国际信息奥林匹克运动会。K国已经举办了国际数学奥林匹克运动会，当时在大会期间，由于K国方面的失误，选手乘坐的巴士被IMO[1]了。让选手两次IMO是作为东道主感到羞耻的事情，所以在国际信息奥林匹克运动会上为了绝对不让选手IMO而制定了对策。

K国使用N个城市作为国际信息奥运会使用的土地。N个城市由M条道路连接，这些道路可以双向通行。每一条路都连接着两个不同的城市，道路之间不会在城市以外的地方相交。另外，K国的城市全部由数字管理。

调查了过去让IMO的原因，结果发现原因是巴士移动中司机读错了城市的数字。因此，为了在这次大会上减少读错，决定将城市的号码按照某种程度容易理解的顺序在驾驶中变得容易检查。具体来说，在巴士可以循环的路线，也就是沿着几条道路围绕城市的路线中，路线上的城市号码总是单调增加或者单调减少。因为大会的日程未定，所以必须考虑巴士的路线。但是，作为巴士的路线，不考虑在同一城市多次循环的路线。满足该条件的K国的状态称为“好K国的状态”。在不存在总线路径的情况下，K国也是“好K国的状态”。

但是，城市的号码是国民熟悉的，所以不能容易地改变。议会反复讨论的结果是，一天只能更换一次某一条道路上的两个城市之间的数字。离大会召开时间不多了，所以必须在尽可能短的天数内达到“好K国的状态”。

另外，这篇文章是以事实为基础的虚构，K国不是代表选手友好的那个国家。

[1]IMO是指“国际迷路奥运会”这一俚语，本文中解释为“在国际大会上迷路”。