VLSI circuits P42669

Statement

0.53 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.

0.5

(100,60)

(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)

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

(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)

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

(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 $10^4$ , and that the $2n$ numbers that define the pin connections are a permutation of $1 \dots 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

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++