Wire Crossing

Time limit2sMemory limit128 MB

Summary

Find the smallest number of wire segments a path between the two given points must cross without passing through a point where wires meet.

Level: Medium7 of 10
Topics: Shortest path, Graph, Geometry
Solved: No attempts yet

Problem

In a two-dimensional hardware layout, crossing wires need expensive gadgets. You are given $m$ existing straight wires and a new connection from $(x_0, y_0)$ to $(x_1, y_1)$ . The new connection need not be straight, but it may not pass through a point where two or more existing wires already meet.

The start and end points do not lie on an existing wire. Each pair of wires meets in at most one point, and wires do not overlap. Find the minimum number of existing wires that must be crossed, and print that number.

Input

A single test case is given.

Line 1: $m$ , $x_0$ , $y_0$ , $x_1$ , $y_1$ ( $m \le 100$ )
Next $m$ lines: one existing wire from $(x_a, y_a)$ to $(x_b, y_b)$

Every coordinate has absolute value less than $10^5$ .

Output

Print the minimum number of existing wires that must be crossed to connect the start and end points.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
0 1 1 9 1
```
Expected output
```
0
```
Example 3
Input
```
1 0 0 10 0
0 5 10 5
```
Expected output
```
0
```