Rat in a Maze

Given a square grid where 1 is an open cell and 0 is a blocked cell, determine whether there is a path from the top-left cell (0,0) to the bottom-right cell (N-1,N-1), moving only up, down, left or right through open cells, without visiting any cell twice.

Input Format

The first line contains an integer N. Each of the next N lines contains N space-separated integers (0 or 1).

Output Format

Print 1 if such a path exists, otherwise print 0.