VLSI circuits P42669


Statement
 

pdf   zip

html
Some VLSI circuits are designed following a Manhattan pattern. The picture shows eight pins connected 1 to 3, 2 to 7, 4 to 8, and 5 to 6. All pins (in black) are located at the bottom of the chip. Pins are connected in pairs by two (blue) vertical wires and one (orange) horizontal wire. Vertical wires use the upper face of the chip, and horizontal wires use the lower face. The chip is punctured (in red) where vertical and horizontal wires meet.
unit=0.07cm

(100,60) linestyle=dotted linewidth=1.2pt linecolor=green

(00,10)(90,10) (00,20)(90,20) (00,30)(90,30) (00,40)(90,40) (00,50)(90,50) (00,60)(90,60) (00,10)(00,60) (10,10)(10,60) (20,10)(20,60) (30,10)(30,60) (40,10)(40,60) (50,10)(50,60) (60,10)(60,60) (70,10)(70,60) (80,10)(80,60) (90,10)(90,60)

taronja1.0 0.4 0.0 linestyle=dashed linewidth=1.5pt linecolor=taronja

(10,30)(30,30) (40,30)(80,30) (50,20)(60,20) (20,40)(70,40)

linestyle=solid linewidth=2pt linecolor=blue

(10,10)(10,30) (30,10)(30,30) (40,10)(40,30) (80,10)(80,30) (50,10)(50,20) (60,10)(60,20) (20,10)(20,40) (70,10)(70,40)

linestyle=solid linewidth=2pt linecolor=red fillcolor=red

(10,30)2 (30,30)2 (40,30)2 (80,30)2 (50,20)2 (60,20)2 (20,40)2 (70,40)2

linestyle=solid linewidth=2pt linecolor=black fillcolor=black

(10,10)2 (20,10)2 (30,10)2 (40,10)2 (50,10)2 (60,10)2 (70,10)2 (80,10)2

(10,04)1 (20,04)2 (30,04)3 (40,04)4 (50,04)5 (60,04)6 (70,04)7 (80,04)8

(95,25)h ->(95,22)(95,10) ->(95,28)(95,40)





Since wires must not overlap, some care must be taken to decide the level of each horizontal connexion. Note that vertical connexions are not a problem because they can never overlap. Please compute the minimum number of levels h needed to connect all the pins with no overlaps. In the example, it is impossible to connect the four pins with less than three levels.

Input

Input consists of several cases, each with a number n followed by n pairs of pins. Assume that n is between 1 and 104, and that the 2n numbers that define the pin connections are a permutation of 1 … 2n.

Output

For every case, print the minimum possible height of the chip.

Public test cases

  • Input

    4  1 3  2 7  4 8  5 6
1  2 1
2  2 3  4 1
2  3 4  1 2

    Output

    3
1
2
1
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++