Jack Straws

Time Limit: 1500 ms Memory Limit: 10000 KiB

Problem Description

 In the game of Jack Straws, a number of plastic or wooden "straws" are
   dumped on the table and players try to remove them one-by-one without
   disturbing the other straws. Here, we are only concerned with if
   various pairs of straws are connected by a path of touching straws.
   You will be given a list of the endpoints for some straws (as if they
   were dumped on a large piece of graph paper) and then will be asked if
   various pairs of straws are connected. Note that touching is
   connecting, but also two straws can be connected indirectly via other
   connected straws.

Input

A problem consists of multiple lines of input. The first line will be
   an integer n (1 < n < 13) giving the number of straws on the table.
   Each of the next n lines contain 4 positive integers, x1 , y1 , x2 and
   y2 , giving the coordinates, (x1 ; y1 ); (x2 ; y2 ) of the endpoints
   of a single straw. All coordinates will be less than 100. (Note that
   the straws will be of varying lengths.) The first straw entered will
   be known as straw #1, the second as straw #2, and so on. The remaining
   lines of input (except for the final line) will each contain two
   positive integers, a and b, both between 1 and n, inclusive. You are
   to determine if straw a can be connected to straw b. When a = 0 = b,
   the input is terminated. There will be no illegal input and there are
   no zero-length straws.
   

Output

You should generate a line of output for each line containing a pair a
   and b, except the final line where a = 0 = b. The line should say
   simply "CONNECTED", if straw a is connected to straw b, or "NOT
   CONNECTED", if straw a is not connected to straw b. For our purposes,
   a straw is considered connected to itself.

Sample Input

7
1 6 3 3
4 6 4 9
4 5 6 7
1 4 3 5
3 5 5 5
5 2 6 3
5 4 7 2
1 4
1 6
3 3
6 7
2 3
1 3
0 0

Sample Output

CONNECTED
NOT CONNECTED
CONNECTED
CONNECTED
NOT CONNECTED
CONNECTED

Hint


Source