시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 256 MB 14 9 8 80.000%

문제

2차원 공간 위에 가로등이 N개 배치되어 있다. i번째 가로등의 위치는 (xi, yi)이고, 각 좌표는 정수이다. 서로 다른 가로등의 위치가 같은 경우는 없다.

두 가로등 i와 j(i < j)가 있을 때, (xi, yj)와 (xj, yi)에 가로등이 있으면, 가로등 i와 j는 균형이 잡혀있다고 한다. 모든 가로등 쌍이 균형잡혀 있는지 아닌지 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 가로등의 수 N이 주어지고, 다음 N개의 줄에 걸쳐서 가로등의 위치 xi, yi가 공백으로 구분해 주어진다.

출력

각 테스트 케이스에 대해서, 모든 가로등의 쌍이 균형 잡혀 있으면 "BALANCED", 아니면 "NOT BALANCED"를 한 줄에 출력한다.

제한

  • 1 ≤ T ≤ 5
  • 2 ≤ N ≤ 200,000
  • -109 ≤ xi, yi ≤ 109

예제 입력 1

2
6
2 3
2 -3
2 1
-2 3
-2 1
-2 -3
6
2 4
2 -3
2 1
-2 3
-2 1
-2 -3

예제 출력 1

BALANCED
NOT BALANCED
W3sicHJvYmxlbV9pZCI6IjE3NDMwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzAwXHViODVjXHViNGYxIiwiZGVzY3JpcHRpb24iOiI8cD4yXHVjYzI4XHVjNmQwIFx1YWNmNVx1YWMwNCBcdWM3MDRcdWM1ZDAgXHVhYzAwXHViODVjXHViNGYxXHVjNzc0IE5cdWFjMWMgXHViYzMwXHVjZTU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWFjMDBcdWI4NWNcdWI0ZjFcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0ICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pXHVjNzc0XHVhY2UwLCBcdWFjMDEgXHVjODhjXHVkNDVjXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjMDBcdWI4NWNcdWI0ZjFcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVhYzAwXHViODVjXHViNGYxIGlcdWM2NDAgaihpICZsdDsgailcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5qPFwvc3ViPilcdWM2NDAgKHg8c3ViPmo8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPilcdWM1ZDAgXHVhYzAwXHViODVjXHViNGYxXHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCwgXHVhYzAwXHViODVjXHViNGYxIGlcdWM2NDAgalx1YjI5NCBcdWFkZTBcdWQ2MTVcdWM3NzQgXHVjN2ExXHVkNjAwXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1YWMwMFx1Yjg1Y1x1YjRmMSBcdWMzMGRcdWM3NzQgXHVhZGUwXHVkNjE1XHVjN2ExXHVkNjAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzAgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWI4NWNcdWI0ZjFcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YWMwMFx1Yjg1Y1x1YjRmMVx1Yzc1OCBcdWM3MDRcdWNlNTgmbmJzcDt4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWJhYThcdWI0ZTAgXHVhYzAwXHViODVjXHViNGYxXHVjNzU4IFx1YzMwZFx1Yzc3NCBcdWFkZTBcdWQ2MTUgXHVjN2ExXHVkNjAwIFx1Yzc4OFx1YzczY1x1YmE3NCAmcXVvdDs8Y29kZT5CQUxBTkNFRDxcL2NvZGU+JnF1b3Q7LCBcdWM1NDRcdWIyYzhcdWJhNzQgJnF1b3Q7PGNvZGU+Tk9UIEJBTEFOQ0VEPFwvY29kZT4mcXVvdDtcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0IiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBUJm5ic3A7JmxlOyA1PFwvbGk+XHJcblx0PGxpPjIgJmxlOyBOICZsZTsgMjAwLDAwMDxcL2xpPlxyXG5cdDxsaT4tMTA8c3VwPjk8XC9zdXA+ICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNzQzMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0cmVldCBsaWdodCBwb3N0cyIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgTiBzdHJlZXQgbGlnaHQgcG9zdHMgb24gYSAyRCBwbGFuZS4gVGhlIGktdGggcG9sZSBpcyBsb2NhdGVkIGF0ICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pLCBhbmQgdGhlIGNvb3JkaW5hdGVzIGFyZSBpbnRlZ2Vycy4gTm8gdHdvIHBvbGVzIGFyZSBsb2NhdGVkIGF0IHRoZSBzYW1lIGNvb3JkaW5hdGVzLjxcL3A+XHJcblxyXG48cD5Gb3IgYW55IHR3byBwb2xlcyBpIGFuZCBqIChpJmx0O2opLCBpZiB0aGVyZSBhcmUgc3RyZWV0IGxpZ2h0IHBvbGVzIGF0ICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+ajxcL3N1Yj4pIGFuZCAoeDxzdWI+ajxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KSBhcyB3ZWxsLCB0aGVuIHdlIHNheSB0aGUgcG9sZXMgaSBhbmQgaiBhcmUgYmFsYW5jZWQuIFlvdSBuZWVkIHRvIGRldGVybWluZSB3aGV0aGVyIHRoZSBnaXZlbiBzdHJlZXQgbGlnaHQgcG9sZXMgYXJlIHBhaXJ3aXNlIGJhbGFuY2VkIChpLmUuLCBiYWxhbmNlZCBmb3IgZXZlcnkgcGFpciBvZiBwb2xlcykuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciBULCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIE4gKHRoZSBudW1iZXIgb2Ygc3RyZWV0IGxpZ2h0IHBvbGVzKS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIHdpbGwgY29udGFpbiB0d28gaW50ZWdlcnMgKHg8c3ViPmk8XC9zdWI+IGFuZCB5PHN1Yj5pPFwvc3ViPilzZXBhcmF0ZWQgYnkgYSB3aGl0ZXNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgaWYgdGhlIHBvbGVzIGFyZSBwYWlyd2lzZSBiYWxhbmNlZCwgdGhlbiBvdXRwdXQgJnF1b3Q7QkFMQU5DRUQmcXVvdDsgYW5kIG90aGVyd2lzZSBvdXRwdXQgJnF1b3Q7Tk9UIEJBTEFOQ0VEJnF1b3Q7IGluIGEgc2luZ2xlIGxpbmUgKHdpdGhvdXQgcXVvdGVzKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=