题目描述

在 “挑棍” 游戏中，若干塑料或木质 “小棍” 被散落在桌上，玩家需尝试逐一捡起小棍且不碰动其他小棍。本题中，我们关注的是不同小棍对之间能否通过相接触的小棍构成的路径相连。你会得到一些小棍端点的坐标（就好像这些小棍散落在一张大坐标纸上），然后需要判断不同的小棍对是否相连。需注意，相接触即相连，而且两根小棍也能通过其他相连的小棍间接相连。

输入格式

输入包含多个测试用例，每个测试用例有多行。第一行是一个整数 $n(1 < n < 13)$，表示桌上小棍的数量。接下来 $n$ 行，每行包含$4$个正整数 $x_1$、$y_1$、$x_2$、$y_2$，给出一根小棍两个端点的坐标 ($x_1$, $y_1$) 和 ($x_2$, $y_2$) ，所有坐标值都小于 100（小棍长度各不相同）。输入的第一根小棍记为小棍 #1，第二根记为小棍 #2，以此类推。当前测试用例除最后一行外的其余行，每行都包含两个正整数$a$ 和 $b$ ，取值都在 1 到 $n$ 之间（包含 $1$和 $n$ ），需判断小棍 $a$ 能否与小棍 $b$ 相连。当 $a$ = $0$且 $b$ = $0$时，当前测试用例结束。当 $n$ = $0$时，输入结束。输入合法且不存在长度为 $0$的小棍。

输出格式

对于除最后一行（$a$ = 0 且 $b$ = 0 ）外，每行包含 $a$ 和 $b$ 的输入行，都应输出一行内容。若小棍 $a$ 与小棍$b$ 相连，输出 “CONNECTED” ；若不相连，输出 “NOT CONNECTED” 。在本题中，一根小棍与其自身视为相连。

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

2
0 2 0 0
0 0 0 1
1 1
2 2
1 2
0 0

0

CONNECTED 
NOT CONNECTED 
CONNECTED 
CONNECTED 
NOT CONNECTED 
CONNECTED
CONNECTED
CONNECTED
CONNECTED

来源

1994年北美中东部地区