You are given an undirected graph with $$$n$$$ vertices. For each pair of vertices $$$(i, j)$$$ ($$$i\neq j$$$), determine whether there exists a Hamiltonian path starting at $$$i$$$ and ending at $$$j$$$.
Recall that a Hamiltonian path is a path consisting of $$$n-1$$$ edges that passes through all vertices exactly once.
The first line contains one integer $$$n$$$ $$$(2 \le n \le 24)$$$ — the number of vertices in the graph.
The $$$i$$$-th of the next $$$n$$$ lines contains a binary string $$$s_i$$$ of length $$$n$$$. Its $$$i$$$-th character is always equal to 0, and for $$$j\neq i$$$ its $$$j$$$-th character is equal to $$$1$$$ if there is an edge between vertices $$$i$$$ and $$$j$$$, and 0 otherwise.
It is guaranteed that for any $$$i\neq j$$$, the $$$i$$$-th character of the $$$j$$$-th line coincides with the $$$j$$$-th character of the $$$i$$$-th line.
Print $$$n$$$ lines. In $$$i$$$-th of them, print a binary string of length $$$n$$$. Its $$$i$$$-th character must be equal to 0, and $$$j$$$-th character at $$$j\neq i$$$ must be equal to 1 if there is a Hamiltonian path between vertices $$$i$$$ and $$$j$$$, and 0 otherwise.
4 0110 1010 1101 0010
0001 0001 0000 1100
6 010001 101000 010100 001010 000101 100010
010001 101000 010100 001010 000101 100010
4 0111 1011 1101 1110
0111 1011 1101 1110
In the first example, the Hamiltonian path exists between pairs $$$(1, 4)$$$ and $$$(2, 4)$$$.
In the second example, the graph is a cycle of length $$$6$$$. The Hamiltonian path here exists only between pairs of adjacent vertices.
In the third example, we have a complete graph with $$$4$$$ vertices. There exists a Hamiltonian path between each pair of vertices.
