Куат изучает очень много математики. За первые два семестра он прослушал курсы «Алгебра», «Аналитическая геометрия», «Линейная алгебра» и «Математический анализ». Знания по всем этим предметам занимают большую часть его памяти. Свою память он представляет в виде таблицы $$$n \times n$$$. Если клетка памяти занята знаниями, то в таблице это отмечено точкой. Если она еще свободна — звездочкой. Будучи настоящим математиком, Куат верит, что все предметы и знания по ним должны быть связаны друг с другом (две единицы знаний считаются соседними, если они имеют общую сторону; все единицы считаются связанными между собой, если для любых двух единиц знания $$$A$$$ и $$$B$$$ можно составить цепочку $$$A = v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_k = B$$$, где $$$v_i$$$ и $$$v_{i+1}$$$ — соседние клетки для любого $$$i$$$). Куат очень надеется, что его знания связаны друг с другом. А если нет, то он готов потратить еще один вечер и заполнить знаниям еще один кусок памяти, чтобы они стали связаны. Гарантируется, что у Куата уже есть как минимум две единицы знаний. Сможет ли он добиться того, чтобы все его знания стали связаны после добавления одной единицы знаний?