Gift Exchange Possibility

You are given N participants and an N x N binary matrix P representing the gift exchange restrictions. In this matrix, P[i][j] is 1 if participant i is allowed to give a gift to participant j, and 0 otherwise. A valid gift exchange is possible if every participant can give a gift to someone else such that no one is left out — that is, if there exists a perfect matching in the bipartite graph represented by P.

Your task is to determine whether a complete gift exchange is possible. Formally, find a perfect matching in a bipartite graph where the left and right parts both represent the participants. If such a matching exists, output Possible, otherwise output Not Possible.

The problem can be formulated using the concept of bipartite matching. One common approach is to use a DFS-based algorithm for finding an augmenting path (also known as the Hungarian algorithm or DFS-based matching technique).

The necessary condition for the gift exchange is that every participant is involved in the matching; that is, the matching must cover all N participants.

The formal condition can also be expressed in LaTeX as:

$$ \text{A valid gift exchange exists if } \exists\, \sigma: \{0,1,\ldots,N-1\} \to \{0,1,\ldots,N-1\} \text{ (a bijection) such that } P[i][\sigma(i)] = 1 \ \forall\, i \in \{0,1,\ldots,N-1\}. $$

inputFormat

The input is read from standard input and has the following format:

N
P[0][0] P[0][1] ... P[0][N-1]
P[1][0] P[1][1] ... P[1][N-1]
...
P[N-1][0] P[N-1][1] ... P[N-1][N-1]

Where:

• N is the number of participants.
• Each of the next N lines contains N integers (0 or 1) separated by spaces representing the N x N matrix P.

outputFormat

Output to standard output either Possible if a valid gift exchange exists (i.e., a perfect matching is found), or Not Possible if it does not.

## sample

4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

Possible