Network Reliability under Single Edge Failure

You are given a network represented as an n × n adjacency matrix. Each entry in the matrix is either 0 or 1, where a 1 represents a direct connection (edge) between two nodes, and 0 indicates no direct connection. The network is undirected, meaning the matrix is symmetric.

Your task is to determine whether the network remains connected after the failure (i.e., removal) of any single channel (edge). In other words, for every edge e present in the network, if we remove e, the remaining graph should be connected. A graph is connected if there is a path between every pair of nodes. Formally, for any two nodes u and v, there must exist a path connecting them after the removal of any single edge.

This property can be summarized by the following condition in LaTeX format:

\(\forall e \in E, \;% \text{the graph } G \setminus \{e\} \text{ is connected} \)

If the network satisfies this property, output True; otherwise, output False.

inputFormat

The input is given via standard input and has the following format:

n
row1
row2
...
rown

Here, n is the number of nodes in the network. Each of the following n lines contains n space-separated integers (either 0 or 1) representing the adjacency matrix of the network.

outputFormat

Output a single line to standard output: True if the network remains connected after the removal of any single edge, and False otherwise.

## sample

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

True