완전한 분해

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

• $V(G_1 \times G_2) = V(G_1) \times V(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,\, u_1,\, v_1,\, u_2,\, v_2,\, \dots,\, u_N,\, v_N$이 가 되도록 해야 한다.

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

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

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

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