Ivan正在为他的爵士乐队计划一场规模盛大的欧洲巡演。在欧洲一共有 $n$ 个城市，编号依次为 $1$ 到 $n$ 。Ivan计划举办 $d$ 场演出，分别在城市 $a_1,a_2,...,a_d$ ，并且严格遵循这个顺序，而且不会在同一个城市连续巡演两次（即 $a_i \neq a_{i+1}$ ），但在整个过程中，他可能在一个城市巡演多次。最终，他一定会回到开始的城市进行巡演（即 $a_1=a_d$ ）。

Ivan每次总是选择搭乘一趟从 $a_i$ 到$a_{i+1}$ 的直达航班。然而，他希望变得聪明一些，尽量节省机票的开支。你也知道，机票的价格取决于供给和需求，比如一张单程票可能会比相同目的地的双程票还要贵。

一共有两种可以购买的机票：

1.从a到b的单程票，每张只能从a飞到b一次，但不能从b飞到a。

2.从a到b的双程票，只需购买一张，就能从a飞到b一次，然后从b飞回a一次，但先从b飞回a是不允许的。当然，你也可以选择从a飞到b之后就再也不返回a。

给定可以购买的机票集合，每种机票都是无限量供应的。请帮助Ivan找到一种最省钱的方案。你可以认为合法方案必然存在。