One day Alice was cleaning up her basement when she noticed something very curious: an infinite set of wooden pieces! Each piece was made of five square tiles, with four tiles adjacent to the fifth center tile:  [Image]  By the pieces lay a large square wooden board. The board is divided into $n^2$ cells arranged into $n$ rows and $n$ columns. Some of the cells are already occupied by single tiles stuck to it. The remaining cells are free.

Alice started wondering whether she could fill the board completely using the pieces she had found. Of course, each piece has to cover exactly five distinct cells of the board, no two pieces can overlap and every piece should fit in the board entirely, without some parts laying outside the board borders. The board however was too large for Alice to do the tiling by hand. Can you help determine if it's possible to fully tile the board?


-----Input-----

The first line of the input contains a single integer $n$ ($3 \leq n \leq 50$) — the size of the board.

The following $n$ lines describe the board. The $i$-th line ($1 \leq i \leq n$) contains a single string of length $n$. Its $j$-th character ($1 \leq j \leq n$) is equal to "." if the cell in the $i$-th row and the $j$-th column is free; it is equal to "#" if it's occupied.

You can assume that the board contains at least one free cell.


-----Output-----

Output YES if the board can be tiled by Alice's pieces, or NO otherwise. You can print each letter in any case (upper or lower).


-----Examples-----
Input
3
#.#
...
#.#

Output
YES

Input
4
##.#
#...
####
##.#

Output
NO

Input
5
#.###
....#
#....
###.#
#####

Output
YES

Input
5
#.###
....#
#....
....#
#..##

Output
NO



-----Note-----

The following sketches show the example boards and their tilings if such tilings exist:  [Image]

Difficulty: interview

Starter code:

Solutions:
n = int(input())

board =[]

for i in range(n):
    board.append(list(input()))
    
f = 1
for i in range(n):
    for j in range(n):
        if board[i][j] == '.':
            if i < n - 2 and j < n - 1 and j > 0 and board[i+1][j] == '.' and board[i+2][j] == '.' and board[i+1][j-1] == '.' and board[i+1][j+1] == '.':
                board[i+1][j] = '#'
                board[i+2][j] = '#'
                board[i+1][j-1] = '#'
                board[i+1][j+1] = '#'
            else:
                f = 0
                break

if f == 1:
    print("YES")
else:
    print("NO") 

n = int(input())
board = [[c for c in input()] for _ in range(n)]
# x = row
for x in range(n):
    # y = col
    for y in range(n):
        if board[x][y] == ".":
            if y == (n-1) or x >= (n-2) or y==0:
                print ("NO")
                return
            board[x][y] = "#"
            if board[x+1][y-1] == "#":
                print ("NO")
                return
            board[x+1][y-1] = "#"
            if board[x+1][y] == "#":
                print ("NO")
                return
            board[x+1][y] = "#"
            if board[x+1][y+1] == "#":
                print ("NO")
                return
            board[x+1][y+1] = "#"
            if board[x+2][y] == "#":
                print ("NO")
                return
            board[x+2][y] = "#"
print ("YES")

n = int(input())
board = [list(input()) for _ in range(n)]

def f(i, j):
    if j == 0 or j == n - 1:
        return False
    if i >= n - 2:
        return False
    if '#' in (board[i + 1][j - 1], board[i + 1][j], board[i + 1][j + 1], board[i + 2][j]):
        return False
    return True

def g(i, j):
    board[i][j] = '#'
    board[i + 1][j - 1] = '#'
    board[i + 1][j] = '#'
    board[i + 1][j + 1] = '#'
    board[i + 2][j] = '#'

for i in range(n):
    for j in range(n):
        if board[i][j] == '.':
            if not f(i, j):
                print('NO')
                return
            g(i, j)

print('YES')


n = int(input().strip())
grid = [list(input().strip()) for _ in range(n)]
for i in range(1, n-1):
	for j in range(1, n-1):
		if grid[i][j] == '.' and grid[i][j+1] == '.' and grid[i][j-1] == '.' and grid[i+1][j] == '.' and grid[i-1][j] == '.':
			grid[i][j] = '#'
			grid[i][j+1] = '#'
			grid[i][j-1] = '#'
			grid[i+1][j] = '#'
			grid[i-1][j] = '#'

for i in range(n):
	for j in range(n):
		if grid[i][j] == '.':
			print('NO')
			quit()

print('YES')

def can(i, j):
    return 0 < i < n - 1 and 0 < j < n - 1 and g[i][j + 1] and g[i + 1][j] and g[i][j - 1] and g[i - 1][j] and g[i][j]


def fill(i, j):
    g[i][j] = 0
    g[i + 1][j] = 0
    g[i - 1][j] = 0
    g[i][j + 1] = 0
    g[i][j - 1] = 0


n = int(input())
g = []
for _ in range(n):
    g.append([1 if x == '.' else 0 for x in input()])

for i in range(n):
    for j in range(n):
        if can(i, j):
            fill(i, j)

v = True

for i in range(n):
    for j in range(n):
        if g[i][j]:
            v = False

print("YES" if v else "NO")


def try_t(i, j):
	if i < 0 or i >= n or j < 0 or j >= n:
		return False
	if A[i][j] == "#":
		return False
	A[i][j] = "#"
	return True

n = int(input())

A = []
for i in range(n):
	s = input()
	B = []
	for elem in s:
		B.append(elem)
	A.append(B)
T = True
for i in range(n):
	for j in range(n):
		if A[i][j] == '.':
			a1 = try_t(i + 1, j)
			a2 = try_t(i + 2, j)
			a3 = try_t(i + 1, j + 1)
			a4 = try_t(i + 1, j - 1)
			if not(a1 and a2 and a3 and a4):
				T = False
				break
if T:
	print("YES")
else:
	print("NO")

import sys

n = int(input())
B = [list(input()) for _ in range(n)]

def ok(x,y):
    return 0 <= x < n and 0 <= y < n

def try_add(i,j):
    if ok(i,j) and B[i][j] == '.':
        B[i][j] = '#'
        return True
    return False

def add_plus(i,j):
    if not try_add(i,j): return False
    if not try_add(i+1,j): return False
    if not try_add(i+2,j): return False
    if not try_add(i+1,j-1): return False
    if not try_add(i+1,j+1): return False
    return True

for i in range(n):
    for j in range(n):
        if B[i][j] == '.':
            if not add_plus(i,j):
                print('NO')
                return
print('YES')


n = int(input())
a = []
for i in range(n):
    a.append(list(input()))

for i in range(n):
    for j in range(n):
        if a[i][j] == '.':
            if n - i < 3 or j == 0 or j == n - 1 or a[i + 1][j] == '#'\
                    or a[i + 2][j] == '#' or a[i + 1][j + 1] == '#' or a[i + 1][j - 1] == '#' or a[i][j] == '#':
                print('NO')
                return

            a[i][j] = '#'
            a[i + 1][j] = '#'
            a[i + 2][j] = '#'
            a[i + 1][j - 1] = '#'
            a[i + 1][j + 1] = '#'
print('YES')


def step(a, b):
    if a > n - 3 or b == 0 or b == n - 1 or l[a + 1][b] == '#' or l[a + 2][b] == '#' or l[a + 1][b - 1] == '#' or l[a + 1][b + 1] == '#':
        return False
    else:
        l[a] = l[a][:b] + '#' + l[a][b + 1:]
        l[a + 1] = l[a + 1][:b - 1] + '###' + l[a + 1][b + 2:]
        l[a + 2] = l[a + 2][:b] + '#' + l[a + 2][b + 1:]
        return True

n = int(input())
l = [input() for i in range(n)]
ans = 'YES'
for i in range(n):
    for j in range(n):
        if l[i][j] == '.' and not step(i, j):
            ans = 'NO'
print(ans)

# Please DON'T hack me! TY!
import sys


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = self.next_line()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_line(self, _map=str):
        return list(map(_map, sys.stdin.readline().split()))

    def next_int(self):
        return int(next(self))

    def solve(self):
        n = self.next_int()
        ss = [[s for s in next(self)] for _ in range(0, n)]
        for i in range(0, n):
            for j in range(0, n):
                if ss[i][j] == '.':
                    if j == 0 or j == n - 1 or i >= n - 2:
                        print('NO')
                        return
                    if ss[i + 1][j - 1] != '.' or ss[i + 1][j] != '.' or ss[i + 1][j + 1] != '.' or ss[i + 2][j] != '.':
                        print('NO')
                        return
                    ss[i + 1][j - 1] = '#'
                    ss[i + 1][j] = '#'
                    ss[i + 1][j + 1] = '#'
                    ss[i + 2][j] = '#'
        print('YES')


def __starting_point():
    Main().solve()

__starting_point()

n = int(input())
grid = [list(input()) for _ in range(n)]

work = True
for i in range(n):
	for j in range(n):
		if grid[i][j] != '.': continue
		# We have to fill down
		pos = [(i, j), (i + 1, j), (i + 2, j), (i + 1, j - 1), (i + 1, j + 1)]
		for r, c, in pos:
			if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] == '#':
				# Invalid
				work = False
				break
			grid[r][c] = '#'
		else: continue
		break
	else: continue
	break
if work:
	print("YES")
else:
	print("NO")

import math
from decimal import Decimal
def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return n,b


def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return n,b,c


def dv():
	n, m = list(map(int, input().split()))
	return n,m


def dva():
	n, m = list(map(int, input().split()))
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return n,m,b


def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return n,b,m,c


def dvs():
	n = int(input())
	m = int(input())
	return n, m


n = int(input())
a = []
for i in range(n):
	s = input()
	s = list(s)
	a.append(s)
for i in range(1, n - 1):
	for j in range(1, n - 1):
		if a[i][j] == '.' and a[i][j + 1] == '.' and a[i][j - 1] == '.' and a[i - 1][j] == '.' and a[i + 1][j] == '.':
			a[i][j], a[i][j + 1], a[i][j - 1], a[i - 1][j], a[i + 1][j] = '#', '#', '#', '#', '#'
f = True
for i in a:
	for j in i:
		if j == '.':
			f = False
if f:
	print('YES')
else:
	print('NO')


def solve():
    n = int(input())
    b = [list(input()) for _ in range(n)]
    for i in range(n - 2):
        if b[i][0] == '.' or b[i][-1] == '.':
            return 'NO'
        for j in range(1, n - 1):
            if b[i][j] == '.':
                chg = [(i + 1, j), (i + 2, j), (i + 1, j - 1), (i + 1, j + 1)]
                for x, y in chg:
                    if b[x][y] == '#':
                        return 'NO'
                    b[x][y] = '#'

    for i in range(n - 2, n):
        for j in range(n):
            if b[i][j] == '.':
                return 'NO'

    return 'YES'


print(solve())


n = int(input())
arr = [[x for x in input()] for _ in range(n)]
move = [(1, -1), (1, 0), (1, 1), (2, 0)]
for i in range(n):
    for j in range(n):
        if arr[i][j] == '.':
            arr[i][j] = '#'
            for m in move:
                mi, mj = i + m[0], j + m[1]
                if 0 <= mi < n and 0 <= mj < n and arr[mi][mj] == '.':
                    arr[mi][mj] = '#'
                else:
                    print('NO')
                    return
print('YES')


def mp():
    return map(int, input().split())

n = int(input())
a = [[j for j in input()] for i in range(n)]

fail = False
for i in range(n):
    for j in range(n):
        if a[i][j] == '#':
            continue
        if (i + 1 < n and a[i + 1][j] == '.') and (i + 2 < n and a[i + 2][j] == '.') and (i + 1 < n and j + 1 < n and a[i + 1][j + 1] == '.') and (i + 1 < n and j - 1 >= 0 and a[i + 1][j - 1] == '.'):
            a[i][j] = '#'
            a[i + 1][j] = '#'
            a[i + 2][j] = '#'
            a[i + 1][j + 1] = '#'
            a[i + 1][j - 1] = '#'
        else:
            fail = True
        
    if fail:
        break
    
for i in a:
    for j in i:
        if j != '#':
            fail = True
            break

if fail:
    print('NO')
else:
    print('YES')

n = int(input())
matrix = []
for i in range(n):
    matrix.append(list(input()))
for i in range(n-2):
    for j in range(1, n-1):
        if matrix[i][j]=='.':
            if matrix[i+1][j]=='.' and matrix[i+2][j]=='.' and matrix[i+1][j-1]=='.' and matrix[i+1][j+1]=='.':
                matrix[i][j]='#'; matrix[i+1][j]='#'; matrix[i+2][j]='#'; matrix[i+1][j-1]='#'; matrix[i+1][j+1]='#'
            else: print('NO'); return
for i in range(n):
    for j in range(n):
        if matrix[i][j]=='.': print('NO'); return
print('YES')


import io, sys, atexit, os

import math as ma
from decimal import Decimal as dec
from itertools import permutations
from random import randint as rand


def li ():
	return list (map (int, input ().split ()))


def num ():
	return map (int, input ().split ())


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


def lcm ( x, y ):
	gg = find_gcd (x, y)
	return (x * y // gg)


mm = 1000000007
yp = 0
def solve ():
	t=1
	for _ in range(t):
		n=nu()
		x=[0]*n
		for i in range(n):
			x[i]=[0]*n
			pp=input()
			for j in range(n):
				if(pp[j]=="."):
					x[i][j]=0
				else:
					x[i][j]=1
		while(True):
			fl=False
			for i in range(n):
				for j in range(n):
					if((i-1)>=0 and (i+1)<n and (j-1)>=0 and (j+1)<n):
						if(x[i][j]==0 and x[i-1][j]==0 and x[i+1][j]==0 and x[i][j+1]==0 and x[i][j-1]==0):
							fl=True
							x [ i ] [ j ] = 1
							x [ i - 1 ] [ j ] =1
							x [ i + 1 ] [ j ] =1
							x [ i ] [ j + 1 ] =1
							x [ i ] [ j - 1 ] =1
							break
				if(fl):
					break
			if(fl==False):
				break
		pw=True
		for i in range(n):
			for j in range(n):
				if(x[i][j]==0):
					pw=False
		if(pw):
			print("YES")
		else:
			print("NO")



def __starting_point():
	solve ()
__starting_point()

#codeforces1150B_live
gi = lambda : list(map(int,input().strip().split()))
n, = gi()
m = [list(input()) for e in range(n)]
for k in range(1,n-1):
	for j in range(1,n-1):
		if m[k-1][j] == m[k+1][j] == m[k][j-1] == m[k][j+1] == m[k][j] == ".":
			m[k-1][j] = m[k+1][j] = m[k][j-1] = m[k][j+1] = m[k][j] = "#"
for k in range(n):
	for j in range(n):
		if m[k][j] == ".":
			print("NO")
			return
print("YES")


n = int(input())
visit = set()
A = [['#'] * n] + [list(input()) for _ in range(n)] + [['#'] * n]
for i in range(len(A)):
    A[i] = ['#'] + A[i] + ['#']
for i in range(1, len(A) - 1):
    for j in range(1, len(A) - 1):
        if A[i][j] == '.' and i * 10 ** 5 + j not in visit:
            f = 1
            for kek, lol in (i, j + 1), (i, j - 1), (i - 1, j), (i + 1, j):
                if A[kek][lol] != '.' or kek * 10 ** 5 + lol in visit:
                    f = 0
            if f:
                for kek, lol in (i, j + 1), (i, j - 1), (i - 1, j), (i + 1, j):
                    visit.add(kek * 10 ** 5 + lol)
                    visit.add(i * 10 ** 5 + j)
        elif A[i][j] == '#':
            visit.add(i * 10 ** 5 + j)
if len(visit) == n * n:
    print('YES')
else:
    print('NO')

kk=lambda:list(map(int,input().split()))
ll=lambda:list(kk())
def check(i,j):
	if 0 <= i < n and 0 <= j < n:
		if ls[i][j] == 0:
			ls[i][j] = 1
			return True
	return False

n = int(input())
ls = [None]*n
for i in range(n):
	ls[i] = [(1 if i == "#" else 0) for i in input()]
for i in range(n):
	for j in range(n):
		if ls[i][j] == 1: continue
		if check(i, j) and check(i+1, j) and check(i+2,j) and check(i+1, j+1) and check(i+1, j-1):
			pass
		else:
			print("NO")
			return
print("YES")


n=int(input())
mat=[]
for i in range(n):
    mat.append(list(input()))
for i in range(1,n-1):
    for j in range(1,n-1):
        if mat[i][j]=='.':
            if mat[i+1][j]=='.' and mat[i-1][j]=='.' and mat[i][j-1]=='.' and mat[i][j+1]=='.':
                mat[i+1][j]='#'
                mat[i-1][j]='#'
                mat[i][j-1]='#'
                mat[i][j+1]='#'
                mat[i][j]='#'
#print(mat)
cnt=0
for i in range(n):
    for j in range(n):
        if mat[i][j]=='#':
            cnt+=1 
print('YES' if cnt==n*n else 'NO')

n = int(input())
a = [list(input()) for _ in range(n)]
for q in range(n):
    for q1 in range(n):
        if a[q][q1] == '.':
            if q+2 < n and 0 < q1 and q1+1 < n:
                if a[q+1][q1-1] == a[q+1][q1] == a[q+1][q1+1] == a[q+2][q1] == '.':
                    a[q][q1] = a[q + 1][q1 - 1] = a[q + 1][q1] = a[q + 1][q1 + 1] = a[q + 2][q1] = '#'
                    continue
            print('NO')
            return
print('YES')


n=int(input())
tab=[]
for i in range(n):
    a=list(input())
    tab.append(a)
for i in range(i):
    for j in range(n):
        if 0<i<n-1 and 0<j<n-1 and tab[i-1][j]==tab[i+1][j]==tab[i][j+1]==tab[i][j-1]==tab[i][j]=='.':
            tab[i][j]='#'
            tab[i-1][j]='#'
            tab[i+1][j]='#'
            tab[i][j-1]='#'
            tab[i][j+1]='#'
for i in range(n):
    for j in range(n):
        if tab[i][j]=='.':
            print('NO')
            return
print('YES')


n = int(input())
field = [list(input()) for i in range(n)]
ans = 1
for i in range(n):
    for j in range(n):
        if field[i][j] == ".":
            if i > n - 3 or j == n - 1 or field[i+1][j] != "." or field[i+2][j] != "." or field[i+1][j+1] != "." or field[i+1][j-1] != ".":
                ans = 0
                break
            field[i+1][j] = "#"
            field[i+2][j] = "#"
            field[i+1][j+1] = "#"
            field[i+1][j-1] = "#"
    if ans == 0:
        break
if ans == 1:
    print("YES")
else:
    print("NO")


n=int(input())
a=[]
fin=[]
for i in range(n):
    b=input()
    v=[0]*len(b)
    a.append(b)
    fin.append(v)

for i in range(n):
    for j in range(n):
        if(a[i][j]=='#'):
            fin[i][j]=1

for i in range(1,n-1):
    for j in range(1,len(a[i])-1):
        if(a[i][j]=='.' and a[i-1][j]=='.' and a[i][j+1]=='.' and a[i][j-1]=='.' and a[i+1][j]=='.' and fin[i][j]==0 and fin[i-1][j]==0 and fin[i][j+1]==0 and fin[i][j-1]==0 and fin[i+1][j]==0):
            fin[i][j]=fin[i-1][j]=fin[i][j+1]=fin[i][j-1]=fin[i+1][j]=1
poss=0
for i in range(n):
    for j in range(n):
        if(fin[i][j]==0):
            poss=1
            break
if(poss):
    print('NO')
else:
    print('YES')