TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

93.8% (15/16)

Submission's AC Ratio

29.2% (19/65)

Description

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

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

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

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

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

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

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

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

Input Format

輸入的第一行為一整數n (1 ≤ n ≤ 100 000) ,代表橫桿數。橫桿由1 編號到n。
接下來的n 行每一行代表一個橫桿的連接情形,意即第i 行代表編號為i 的橫桿之連接
情形。這裡每一行有兩個整數l 及r,並以一個空白分開。這兩個整數分別代表此橫桿
左右兩端所掛的東西。如果此整數為 -1 則代表掛的是玩具,否則代表掛的是編號為此
整數的橫桿。
如果編號為i 的橫桿之下掛有其他橫桿,則其編號必大於i。編號為1 的橫桿為最上面
的橫桿。

Output Format

輸出為一行,且此行僅有一整數,代表將此吊飾調整成艾可喜歡樣子所需的最少互換
數目。如果此吊飾不可能調整成艾可喜歡的樣子則輸出 -1。

Sample Input

6
2 3
-1 4
5 6
-1 -1
-1 -1
-1 -1

Sample Output

2

Hints

Problem Source

原TIOJ1736 / APIO '07

Subtasks

For Testdata: 0 ~ 0, Score: 2
For Testdata: 1 ~ 1, Score: 2
For Testdata: 2 ~ 2, Score: 2
For Testdata: 3 ~ 3, Score: 2
For Testdata: 4 ~ 4, Score: 2
For Testdata: 5 ~ 5, Score: 2
For Testdata: 6 ~ 6, Score: 2
For Testdata: 7 ~ 7, Score: 2
For Testdata: 8 ~ 8, Score: 2
For Testdata: 9 ~ 9, Score: 2
For Testdata: 10 ~ 10, Score: 2
For Testdata: 11 ~ 11, Score: 2
For Testdata: 12 ~ 12, Score: 2
For Testdata: 13 ~ 13, Score: 2
For Testdata: 14 ~ 14, Score: 2
For Testdata: 15 ~ 15, Score: 2
For Testdata: 16 ~ 16, Score: 2
For Testdata: 17 ~ 17, Score: 2
For Testdata: 18 ~ 18, Score: 2
For Testdata: 19 ~ 19, Score: 2
For Testdata: 20 ~ 20, Score: 2
For Testdata: 21 ~ 21, Score: 2
For Testdata: 22 ~ 22, Score: 2
For Testdata: 23 ~ 23, Score: 2
For Testdata: 24 ~ 24, Score: 2
For Testdata: 25 ~ 25, Score: 2
For Testdata: 26 ~ 26, Score: 2
For Testdata: 27 ~ 27, Score: 2
For Testdata: 28 ~ 28, Score: 2
For Testdata: 29 ~ 29, Score: 2
For Testdata: 30 ~ 30, Score: 2
For Testdata: 31 ~ 31, Score: 2
For Testdata: 32 ~ 32, Score: 2
For Testdata: 33 ~ 33, Score: 2
For Testdata: 34 ~ 34, Score: 2
For Testdata: 35 ~ 35, Score: 2
For Testdata: 36 ~ 36, Score: 2
For Testdata: 37 ~ 37, Score: 2
For Testdata: 38 ~ 38, Score: 2
For Testdata: 39 ~ 39, Score: 2
For Testdata: 40 ~ 40, Score: 2
For Testdata: 41 ~ 41, Score: 18
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536
10 1000 65536
11 1000 65536
12 1000 65536
13 1000 65536
14 1000 65536
15 1000 65536
16 1000 65536
17 1000 65536
18 1000 65536
19 1000 65536
20 1000 65536
21 1000 65536
22 1000 65536
23 1000 65536
24 1000 65536
25 1000 65536
26 1000 65536
27 1000 65536
28 1000 65536
29 1000 65536
30 1000 65536
31 1000 65536
32 1000 65536
33 1000 65536
34 1000 65536
35 1000 65536
36 1000 65536
37 1000 65536
38 1000 65536
39 1000 65536
40 1000 65536
41 1000 65536