완전한 분해

두 무방향 그래프 $G_1$과 $G_2$에 대해, 텐서 곱 $G_1 \times G_2$는 다음과 같이 정의된다.

• $V(G_1 \times G_2) = V(G_1) \times V(G_2)$
• $E(G_1 \times G_2) = \{(u_1,v_1)(u_2,v_2) \mid u_1u_2 \in E(G_1),\, v_1v_2 \in E(G_2)\}$

이러한 텐서 곱을 계산하는 것은 쉽지만, 주어진 그래프 $G$가 비자명한 두 그래프의 텐서 곱으로 표현될 수 있는지, 또 가능하다면 어떤 $G_1, G_2$인지를 찾는 문제는 일반적으로 매우 어려운 문제다.

완전그래프란 모든 정점 쌍이 서로 간선으로 연결된 그래프를 말하며, $n$개의 정점을 가진 완전그래프를 $K_n$이라 한다. 정점의 번호는 $1,2,\dots,n$이다.

어떤 그래프 $G$가 두 완전그래프의 텐서 곱 $G = K_n \times K_m$으로 표현될 수 있다면, 이를 완전한 분해라고 하자.

완전한 분해가 존재하는 그래프 $G$가 주어진다. 여러분은 $G = K_n \times K_m$을 만족하는 $n, m$을 찾아내고, 각 정점 $i$에 대해 대응되는 순서쌍 $(u_i, v_i) \in [1,n] \times [1,m]$을 구해야 한다.

단, 가능한 정답이 여러 개일 수 있으므로, 출력되는 전체 수열 $n,\, m,\, u_1,\, v_1,\, u_2,\, v_2,\, \dots,\, u_N,\, v_N$이 사전순으로 최소가 되도록 해야 한다.

첫 줄에 그래프 $G$의 정점 수 $N$이 주어진다. $(1 \le N \le 1\,000)$

이후 $N$개의 줄에 걸쳐 그래프의 인접 행렬이 주어진다. $i$번째 줄은 길이 $N$의 0과 1로 이루어진 문자열이며, $j$번째 문자가 1이면 정점 $i$와 $j$가 간선으로 연결되어 있음을, 0이면 연결되어 있지 않음을 의미한다.

입력으로 주어지는 그래프 $G$는 항상 완전한 분해가 존재함이 보장된다.

첫 줄에 $n$과 $m$을 공백으로 구분하여 출력한다.

이후 $N$개의 줄에 걸쳐, $i$번째 줄에 정점 $i$에 대응하는 $(u_i, v_i)$를 공백으로 구분하여 출력한다.

출력되는 전체 수열 $n,\, m,\, u_1,\, v_1,\, u_2,\, v_2,\, \dots,\, u_N,\, v_N$이 사전순으로 최소가 되어야 함에 유의하라.