BESTPAIR - More pairs are better

Given an undirected unweighted graph G=(V, E), a match is a collection of edges such that no two edges share a common vertex. In this problem you should collect as many as possible edges that construct matches in the graph.

Input

The first line contains n, the number of vertices in the graph. The next n lines contain n characters of '0' and '1', where '1' at position j in line i means there is an edge (i,j) in the graph.

There are no more than 500 vertices in the graph, and the vertices are labeled from 1 to n inclusive.

Output

Print each edge (pair of vertices) which is part of match collection. Each line contains two values, the vertices' label of the edge.

Example

Input:
6
001000
001000
110111
001010
001100
001000

Output: 5 4 2 3

Added by:Jimmy Tirtawangsa
Date:2016-03-02
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:GAWK BASH C-CLANG C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 FORTRAN GO JAVA JS-RHINO JULIA KTLN LUA NIM NODEJS OBJC OBJC-CLANG PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PROLOG PYTHON PYPY PYPY3 PYTHON3 PY_NBC R RUBY RUST SQLITE SWIFT TCL UNLAMBDA VB.NET
Resource:https://en.wikipedia.org/wiki/Matching_%28graph_theory%29

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.