Minimum Bus Transfers

You are given a starting point (S=(s_x,s_y)) and a destination (D=(d_x,d_y)) in the plane. There are (n) bus lines, where each bus line is represented as a line segment between two points ((x_1,y_1)) and ((x_2,y_2)). A bus can be taken if the starting point or the destination point lies on it (i.e. the point and the line segment intersect). Additionally, you can transfer between two bus lines if their line segments intersect. Your task is to determine the minimum number of bus lines you need to take to travel from (S) to (D). If it is not possible, output (-1).

The geometry part involves checking if two line segments intersect. Two line segments (p_1p_2) and (p_3p_4) are said to intersect if they share at least one point. For the purpose of this problem, intersection includes endpoints and cases where one segment touches the other.

The input begins with the coordinates of (S) and (D), followed by an integer (n) indicating the number of bus lines. Each of the following (n) lines contains four integers representing the endpoints of a bus line: (x_1), (y_1), (x_2), (y_2).

Your program should print the minimum number of bus lines required to travel from (S) to (D) (if a valid route exists), or (-1) otherwise.

inputFormat

The input is read from standard input (stdin) with the following format:

Line 1: Four integers (s_x) (s_y) (d_x) (d_y) representing the start and destination coordinates. Line 2: An integer (n), the number of bus lines. The next (n) lines: Each contains four integers (x_1) (y_1) (x_2) (y_2), which are the endpoints of a bus line.

outputFormat

Print a single integer to standard output (stdout): the minimum number of bus lines required to travel from (S) to (D), or (-1) if it is not possible.## sample

0 0 10 10
4
0 0 5 5
5 5 10 10
5 0 10 5
0 10 10 0

2