thief

Bob the Penguin recently stole a huge wooden board of width W and height H from Barr the Bear without him noticing. He divided the board into W*H cells, with the lower left corner having the coordinate of (1,1) and the upper-right corner having the coordinate of (W+1,H+1).

Feeling happy about himself, he randomly drilled 2*N holes along the width of the wooden board with his tough beak. However, he is not random enough, so there is a certain order in the points he drilled. More precisely, N of the holes lie on height 1 and the remaining N holes lie on height H.

After drilling holes, Bob's beak hurts, so he decided to try something else instead. He paired the 2*N points into N distinct pairs, where each point on row 1 is paired with a point on row H. Each pair is represented as P(A,B), which means point (A,1) and point (B,H) are paired together.

Then he wants to connect each pair of points with some colourful electric wires. Due to his poor eyesight, he cannot differentiate which points are connected together if wires of the same colour intersect. In order words, if P(A,B) and P(C,D) are connected with wires of the same colour, then the wires cannot intersect each other. For example, suppose we have two pairs P(1,2) and P(2,1). Then these two pairs will cross each other when connected with a wire. Therefore, the colour of the wires used to connect these two pairs must be different.

Bob the Penguin does not have wires, so he decides to steal the wires from Barr the Bear again. However, he decides to steal wires such that the number of different colours is minimal (That way, Barr the Bear will not get suspicious). However, he was recently exempted from taking the Common Test, so he had not been studying and was very rusty in his mathematical skills. Can you help him figure out what is the minimal number of colours needed?

Input

The first line contains an integer N (1 ≤ N ≤ 100,000), the number of pairs of points that will be given. The following N lines contain two space-separated integers A and B each, indicating that point (A, 1) and point (B, H) needs to be connected with a wire. (0 ≤ A, B ≤ 1,000,000,000)

Output

Output the minimum number of colours that Bob the Penguin needs to steal.

Grading

Subtask 1 (40%): N ≤ 15.

Subtask 2 (30%): N ≤ 5,000.

Subtask 3 (30%): No Additional Constraints

Subtask 4 (0%): Sample Testcases

Sample Input 1

2
1 1
3 4

Sample Output 1

1

Sample Input 2

2
1 2
2 1

Sample Output 2

2