Компьютерная игра
Джон и Брюс играет военно-стратегическую игру на компьютере. Игра ведется на плоской карте мира. В начале игры Брюс выбирает места для своей армии, а затем Джон должен выбрать стратегические точки для своей армии в соответствии со следующими правилами:
каждой стратегической точкой должны быть точки решетки (x, y) (точкой решетки является точка с целыми координатами) такие, что |x| + |y| < N;
Джон может выбрать любое число стратегических точках;
все стратегические пункты должны быть различны;
каждая из стратегических точек должна быть свободной (т.е. не занятая армией Брюса);
каждая пара различных стратегических точек должна быть связана (возможно, через какие-либо другие стратегические точки).
Две разных точки решетки (x_1, y_1) и (x_2, y_2) связаны, если |x_1 – x_2| + |y_1 – y_2| = 1. Если A, B и С являются стратегическими пунктами, и А с B связаны, а B с C связаны, то А с С также связаны.
Входные данные
Первая строка содержит одно целое Т - количество тестов. Каждый тест начинается со строки, содержащей два целых числа N и M, разделенных одним пробелом. N является количеством, указанном в первом правиле. М - число целых точек на карте мира, уже заняты армией Брюса. Каждая из следующих M строк содержит два целых числа Хk и Yk, разделенных одним пробелом. Каждая точка (Xk, Yk) занята армией Брюса.
Выходные данные
Для каждого теста распечатать одну строку, содержащую ряд способов для Джона выбрать стратегические точки для своей армии.
Ограничения
1 <= T <= 74,
1 <= N <= 7,
1 <= M <= 225,
-7 <= X_k, Y_k <= 7,
Все (X_k, Y_k) будут различны.