City Road Map

Given the road map of a city, write a program that finds the shortest route between two given points.

The road map is represented as a set of line segments in the plane. Some segments are roads; the others are signs that mark a direction in which you may not travel. A segment is a sign if exactly one of its two endpoints lies on another segment while the other endpoint does not; every other segment is a road.

A sign attached at a point $B$ on a road restricts travel through $B$. Suppose the road passes through points $A$ and $C$ on opposite sides of $B$, and let $F$ be the sign's free endpoint. Among the angles the sign makes with the road, you may not move from the side of the obtuse angle toward the side of the acute angle. For example, if angle $ABF$ is acute and angle $CBF$ is obtuse, you may travel from $A$ through $B$ to $C$, but not from $C$ through $B$ to $A$. If the sign meets the road at a right angle, you may not pass through $B$ at all.

Find the shortest route from the start point to the goal point that obeys these rules. The distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.

The first line contains the number of test cases $T$. Each test case has the following form.

The first line of a test case contains the number of segments $n$ ($1 \le n \le 200$). The second line contains $x_s$ and $y_s$, and the third line contains $x_g$ and $y_g$, where $(x_s, y_s)$ is the start point and $(x_g, y_g)$ is the goal point; you must compute the shortest route between them. The start and goal points are different, and the shortest route is always unique.

Each of the next $n$ lines describes one segment in the form $x_{1k}\ y_{1k}\ x_{2k}\ y_{2k}$, the two endpoints of the $k$-th segment. The two endpoints of a segment are different, and no two segments cross; that is, segments always meet at a shared endpoint. All coordinates are non-negative integers not greater than 1000.

For each test case, print the points of the shortest route from the start point to the goal point, in the order they are visited: the start point first, then every point on the route where at least two roads meet, and the goal point last. Print one point per line as its x-coordinate and y-coordinate separated by a single space, then print 0 on the final line of that test case. An intersection point is a point where at least two roads (segments that are not signs) meet, so a point where only a sign touches a road is not printed. If there is no route from the start point to the goal point, print -1 as the only output for that test case.