Problem : 228 - Mobiles

你需要幫你的弟弟艾克買禮物。艾克對禮物有很特殊的品味，而且他只喜歡能調整成他喜好樣子的禮物。
　　
　　你發現了一間賣吊飾的禮品店。這裡所謂的吊飾是一種能吊在天花板上的多層裝飾品。一個吊飾由許多橫桿藉由垂直連接線連接而成。每一根橫桿的兩頭都連有線，可掛上另一根橫桿，或是一個玩具。以下以圖示表示一個吊飾。


　　
如果想讓艾克接受一個吊飾做為禮物，此吊飾必須能經由調整，從而滿足以下條件：
　　　(I)　任意兩個玩具必須在同樣的高度，或是高度僅差一。在這裡所謂的高度是指禮物到達天花板所需經過的橫桿數。
　　　(II)　對任意兩個高度差一的禮物而言，左邊的禮物必須比較低。

　　吊飾可經由所謂交換進行調整。互換的具體定義是選定一個橫桿，取下兩端所掛的東西，左右交換之後再掛回原選定的橫桿。此一動作並不會改變我們從選定的橫桿兩端所取下的東西其內部物件（橫桿或玩具）的順序。

　　因為你正在接受資訊奧林匹亞集訓，所以你決定寫一個程式來決定一個給定的吊飾是否能經由互換而調整成艾可會喜歡的形式。
　　
　　考慮上面的吊飾圖例。艾可不會喜歡這個吊飾。雖然它滿足第一個條件，但並不滿足第二個條件–最左邊的玩具比他右邊的玩具來的高。

　　雖然如此，這個吊飾還是可以調整成艾可喜歡的形式。我們需要進行以下步驟：
　　　1. 首先，交換橫桿1 的左右邊。亦即橫桿2 及橫桿3 的位置會被互換，形成以下的狀態。



　　 2. 接著我們交換橫桿2 的左右邊，亦即將橫桿4 移到橫桿2 的左邊，並將玩具移到橫桿2 的右邊。



　　經由這些調整，此吊飾可以滿足艾可喜歡的條件。意即所有的玩具高度最多差一，而且比較低的玩具會在比較高的玩具左邊。

　　你的工作是當給定一個吊飾時，找出最小數目的互換動作將吊飾調整成艾可喜歡的樣子（如果可能的話）。我們在此假定玩具在調整過程中不會互相卡住。