Problem:
 Score : 700 points    Problem Statement You are given a string s of length n .
Does a tree with n vertices that satisfies the following conditions exist?   The vertices are numbered 1,2,..., n .  The edges are numbered 1,2,..., n-1 , and Edge i connects Vertex u_i and v_i .  If the i -th character in s is 1 , we can have a connected component of size i by removing one edge from the tree.  If the i -th character in s is 0 , we cannot have a connected component of size i by removing any one edge from the tree.   If such a tree exists, construct one such tree.      Constraints  2 \leq n \leq 10^5  s is a string of length n consisting of 0 and 1 .         Input Input is given from Standard Input in the following format:  s       Output If a tree with n vertices that satisfies the conditions does not exist, print -1 .  If a tree with n vertices that satisfies the conditions exist, print n-1 lines.
The i -th line should contain u_i and v_i with a space in between.
If there are multiple trees that satisfy the conditions, any such tree will be accepted.        Sample Input 1 1111      Sample Output 1 -1  It is impossible to have a connected component of size n after removing one edge from a tree with n vertices.       Sample Input 2 1110      Sample Output 2 1 2
2 3
3 4  If Edge 1 or Edge 3 is removed, we will have a connected component of size 1 and another of size 3 . If Edge 2 is removed, we will have two connected components, each of size 2 .       Sample Input 3 1010      Sample Output 3 1 2
1 3
1 4  Removing any edge will result in a connected component of size 1 and another of size 3 .

Solution (Python):



def solve(s):
    n = len(s)

    if s[0] != '1':
        print(-1)
        return
    if s[-1] != '0':
        print(-1)
        return
    for i in range((n - 1) // 2):
        if s[i] != s[n - 2 - i]:
            print(-1)
            return
    edges = [(1, 2)]
    s = s[: n // 2]
    p = 1
    if 3 < n and s[1] == '1':
        p = 2
    for i in range(1, n // 2):
        edges.append((p, i + 2))
        if s[i] == '1':
            p = i + 2
    for i in range(n // 2 + 1, n):
        edges.append((p, i + 1))

    for uv in edges:
        u, v = uv
        print('{} {}'.format(u, v))


def main():
    s = input()

    solve(s)


if __name__ == '__main__':
    main()

Solution (Python):


























import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(S):
    
    if S[-1] == '1':
        return -1
    if S[0] == '0':
        return -1
    size = len(S)
    i = 0
    j = size - 2
    while i < j:
        if S[i] != S[j]:
            return -1
        i += 1
        j -= 1

    
    edges = []
    top = 0
    for i in range(size - 1):
        edges.append((top, i + 1))
        if S[i] == '1': 
            top = i + 1
    return edges

S = input()
ans = solve(S)
if ans == -1:
    print(ans)
else:
    for e in ans:
        print("{} {}".format(e[0] + 1, e[1] + 1))

Solution (Python):
s=input()
n=len(s)
if s[-1]=='1' or s[0]=='0':
    print(-1)
    exit()
for i in range(n-1):
    if s[i]!=s[-i-2]:
        print(-1)
        exit()
edges=[]
par=n
for i in range(n-1,0,-1):
    print(i,par)
    if s[i-1]=='1':
        par=i

Solution (Python):
S = input()
if S[0] == '0' or S[-1] == '1':
    print(-1)
    exit()
flag = True
for i in range((len(S)-1)//2):
    if S[i] != S[-2-i]:
        flag = False
        break
if not flag:
    print(-1)
    exit()

ans = []
now = 1
sub = 0
for c in S[:-1]:
    if c == '1':
        ans.append((now, now+sub+1))
        now += sub+1
        sub = 0
    else:
        sub += 1
        ans.append((now, now+sub))

for elem in ans:
    print(str(elem[0])+' '+str(elem[1]))

Solution (Python):
*S, = map(int, open(0).readline().strip())
N = len(S)
ok = 1
for i in range(N-1):
    if S[i] != S[-2-i]:
        ok = 0
        break
if not ok or S[0] != 1 or S[-1] != 0:
    print(-1)
    exit(0)

E = []
V = [i+1 for i in range(N//2) if S[i]]
p = 1
for v in V:
    for i in range(p, v):
        E.append("%d %d\n" % (i, v))
    p = v

E.append("%d %d\n" % (p, p+1))
p += 1
for i in range(p+1, N+1):
    E.append("%d %d\n" % (p, i))
open(1, 'w').writelines(E)

Solution (Python):
s = input()
N = len(s)
if s[-1] == "1" or s[0] == "0" or s[:N-1] != s[:N-1][::-1]:
    print("-1")
else:
    v = 1
    for i in range(N-1):
        print("{} {}".format(v, i+2))
        if s[i] == "1" and i+1 <= N//2:
            v = i + 2
        else:
            pass

Solution (Python):
def die(): print(-1); exit()

s = input()
n = len(s)
if s[-1] == '1': die()
if s[0] == '0': die()
for i in range(n-1):
    if s[i] != s[-i-2]: die()

root = last = 1
for i in range(n-1):
    last+= 1
    print(root, last)
    if s[i] == '1': root = last

Solution (Python):
S = [int(x) for x in input()]
N = len(S)
if S[0] == 0 or S[-1] == 1 or any(S[i] != S[-i - 2] for i in range(N - 1)):
    print(-1)
    quit()

edge = [(1, 2)]
root, now = 2, 3
for i in range(1, N // 2 + 1):
    edge.append((root, now))
    if S[i] == 1:
        root = now
    now += 1
while now <= N:
    edge.append((root, now))
    now += 1
for s, t in edge:
    print(s, t)

Solution (Python):
s=input()
n=len(s)
for i in range(n-1):
  if s[i]!=s[n-2-i]:
    print(-1)
    exit()
if s[-1]=="1" or s[0]=="0":
  print(-1)
  exit()
G=[]
p=n-1
for i in range(n-1)[::-1]:
  G.append([i+1,p+1])
  if s[i]=="1":
    p=i
for i in range(n-1):
  print(G[i][0],G[i][1])

Solution (Python):
s = input()
n = len(s)
comp = {i+1: True if st == '1' else False for i, st in enumerate(s)}
comp[0] = False


feasible = True
for i in range(n//2 + 1):
    if i == 1 and not (comp[i] and comp[n-i]):
        feasible = False
        break
    elif comp[i] ^ comp[n-i]:
        feasible = False
        break

if not feasible:
    print(-1)
else:
    edge = []
    parent = n
    for i in reversed(range(1, n)):
        edge.append((i, parent))
        if comp[i]:
            parent = i
    for u, v in edge:
        print(u, v)

Solution (Python):
n=input()
n='0'+n
l=len(n)
flag=0
if n!=n[::-1]:
    flag=1
if n[1]=='0':
    flag=1
if flag==0:
    print(1,2)
    c=1
    for i in range(1,l-2):
        if n[i]=='1':
            print(i+1,i+2)
            c=i+1
        else:
            print(c,i+2)
else:
    print(-1)

Solution (Python):

from sys import stdin

s_in = lambda: stdin.readline()[:-1] 
d_in = lambda: int(stdin.readline()) 
ds_in = lambda: list(map(int, stdin.readline().split())) 

S = s_in()
N = len(S)

if S[0] == '0':
    print(-1)
    exit()
elif S[-1] == '1':
    print(-1)
    exit()

for i in range((N-1)//2):
    if S[i] != S[-i-2]:
        print(-1)
        exit()

parent = N
for i in range(N-1, 0, -1):
    s = S[i-1]
    if s == '1':
        print(i, parent)
        parent = i
    else:
        print(i, parent)

Solution (Python):
def solve(s):
    if s[-1] == '1':
        return False
    if s[0] == '0':
        return False
    half = s[:len(s) // 2]
    if half != s[-2:(len(s) - 3) // 2:-1]:
        return False
    head = 1
    master = 1
    buf = []
    for i, c in enumerate(half):
        if c == '0':
            buf.append('{} {}'.format(master, i + 2))
        else:
            buf.append('{} {}'.format(head, i + 2))
            head = master = i + 2
    for i in range(len(half), len(s) - 1):
        buf.append('{} {}'.format(master, i + 2))
    return buf


res = solve(input())
if res == False:
    print(-1)
else:
    print('\n'.join(res))

Solution (Python):
s = input()
ans = []
n = len(s)
a = 1
if s[0] == "0" or s[-1] == "1":
  print(-1)
  exit()
for i in range(n-1):
  if s[i] != s[n-i-2]:
    print(-1)
    exit()
oya = n
for i in range(n-1,0,-1):
  ans.append([oya,i])
  if s[i-1] == "1":
    oya = i
for i in ans:
  print(*i)

Solution (Python):
s = input()
n,m,m2 = len(s),1,2
if 1-int(s[0]) or int(s[-1]) or any(s[i]!=s[n-i-2] for i in range(n-1)): print(-1)
else:
	for i in range(n-1):
		print(m,m2)
		if int(s[i]): m = m2
		m2+=1

Solution (Python):
s = input()
n = len(s)
if s[0] == '1' and s[-1] == '0' and s[:n//2] == s[(n-1)//2:-1][::-1]:
    q = []
    now = 0
    for i in range(n):
        m = s[i]
        if m == '1':
            now = str(i+1)
            while q:
                print( q.pop() + ' ' + now)
        q.append( str(i+1))
    while q:
        a = q.pop()
        if now != a:
            print( a + ' ' + now)
else:
    print(-1)

Solution (Python):
a=input()
b=a[:-1]
if a[0]=='0' or a[-1]=='1' or b!=b[::-1]:
  print(-1)
  exit()
p=1
for i in range(2,len(a)+1):
  print(p,i)
  if a[i-2]=='1':
    p=i

Solution (Python):
S = input()

L = len(S)
if S[0]=="0" or S[-1]=="1":
    print(-1)
    exit()
for i in range(L-2):
    if S[i] != S[L-2-i]:
        print(-1)
        exit()

pv = 1
for i in range(L-1):
    nv = i+2
    
    if S[i]=="1":
        print(pv,nv)
        pv = nv
    
    else:
        print(pv,nv)

Solution (Python):
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('e1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    s = list(map(int, read_str()))
    n = len(s)
    if s[0] != 1:
        return -1
    if s[n - 1] != 0:
        return -1
    for i in range(n - 1):
        if s[i] != s[n - 2 - i]:
            return -1
    x = [i for i in range(n) if s[i] == 1]
    k = len(x)
    body = list(range(1, k + 2))
    res = [[body[i], body[i + 1]] for i in range(k)]
    p = k + 2
    for j in range(1, k):
        for l in range(x[j] - x[j-1] - 1):
            edge = [body[j], p]
            p += 1
            res.append(edge)
    return res


def main():
    res = solve()
    if res == -1:
        print(res)
        return
    for edge in res:
        print(*edge)


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
n = len(s)
if s[-1] == '0' and s[0] == '1' and s[n - 2] == '1' and s[:n - 1] == s[n - 2 :: -1]:
    
    
    
    i = 0
    j = 1
    while j <= n - 2:
        if s[j] == '1':
            for k in range(i, j):
                print(k + 1, j + 1)
            i = j
            j = j + 1
        else:
            j += 1
    print(n - 1, n)

else:
    print(-1)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = lc()
n = len(s)

if s[0] == "0" or s[-1] == "1" or s[-2] == "0":
    print(-1)
    
elif s[:(n-1)//2] != s[n-2:n//2-1:-1]:
    print(-1)
    
else:
    par = n
    cur = n-1
    print(n,n-1)
    
    if n > 2:
        for si in s[-3::-1]:
            cur -= 1
            print(par,cur)
            if si == "1":
                par = cur

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    s = [int(c) for c in S()]
    if s[0] != 1 or s[-1] == 1:
        return -1
    n = len(s)
    for i in range(1,n):
        if s[i-1] != s[n-i-1]:
            return -1

    q = collections.deque()
    for i in range(1,n):
        if s[i] == 1:
            q.append(i+1)
    q.append(n)
    c = 1
    r = []
    for i in range(1,n):
        if c == i:
            c = q.popleft()
        r.append('{} {}'.format(i,c))

    return '\n'.join(r)


print(main())

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

S = raw_input()
if S[-1] == '1' or S[0] == '0':
    print -1
    exit()

S = S[:-1]
N = len(S)

for i in range(N):
    if S[i] != S[N - i - 1]:
        print -1
        exit()

pos = 2
print "1 2"
for i in range(1, N):
    print pos, i + 2
    if S[i] == '1':
        pos = i + 2

Solution (Python):

def f(s):
    n = len(s)
    if s[-1] == '1' or s[-2] == '0' or s[0] == '0':
        print(-1)
        return
    i,j = 0,n-2
    while i < j:
        if s[i] != s[j]:
            print(-1)
            return
        i+=1
        j-=1
    e = []
    k = 0
    for i, c in enumerate(s):
        if c == '1':
            if i == 0:
                k = 0
                continue
            for j in range(k+1): e.append((i-k+j, i+1))
            k = 0
        else: k += 1
    e.append((n-k, n))
    for u,v in e: print(u,v)
f(input())

Solution (Python):
s = input()
n = len(s)
s2 = s[:n-1]

if s[0] != '1' or s[-1] != '0' or (s2[::-1] != s2):
    print("-1")
    exit(0)

ans = "{0} {1}"
par = n
for i in range(n-2,-1,-1):
    print(ans.format(par,i+1))
    if s[i] == '1':
        par = (i+1)

Solution (Python):
s=input()
n=len(s)
flag=False
for i in range(n//2):
    if s[i]!=s[-i-2]:
        flag=True
if flag or s[0]=="0" or s[-1]=="1":
    print(-1)
else:
    print("2 1")
    head=2
    for i in range(3,n//2+2):
        print(str(i)+" "+str(head))
        if s[i-2]=="1":
            head=i
    i=n//2+2
    while i<=n:
        print(str(i)+" "+str(head))
        i+=1

Solution (Python):
x = input()
n = len(x)
ret=[]
if x[n-1]=="1" or x[0]=="0" or x[:-1]!=x[-2::-1]:
    print (-1)
else:
    a=1
    for i in range(n-1):
        print ("{0} {1}".format(a, i+2))
        if x[i] == "1":
            a=i+2

Solution (Python):
x = [c  for c in input()]

n = len(x)
ret=[]
for i in range(n-1):
    ret.append([0,0])

if x[n-1] == "1":
    print (-1)
elif x[0] == "0":
    print (-1)
else:
    flg = 1
    for i in range(n-1):
        if x[i] != x[n-1-i-1]:
            flg = 0
    if flg == 0:
        print (-1)
    else:
        a=1
        for i in range(n-1):
            if x[i] == "1":
                ret[i] = [a,i+2]
                a=i+2
            else:
                ret[i] = [a,i+2]
        
        for i in range(n-1):
            print ("{0} {1}".format(ret[i][0], ret[i][1]))

Solution (Python):
s = input()
l = len(s)

if s[0] != '1' or s[-2] != '1' or s[-1] != '0':
  print('-1')
  exit()
if s[:-1] != s[:-1][::-1]:
  print('-1')
  exit()


e = [l] + [-1] * (l-1)
now = 0
h = (l-1) // 2
for i in range(h, 0, -1):
  c = s[i]
  if c == '0':
    continue
  
  e[now] = l - i
  e[l-i-1] = l
  now = l-i-1

for i, a in enumerate(e):
  for j in range(i+2, a+1):
    print(i+1, j)

Solution (Python):


def solve():
    s = input()
    n = len(s)

    if s[0] != '1' or s[-1] != '0':
        print(-1)
        return
    for i in range(n // 2):
        if s[i] != s[-(i + 2)]:
            print(-1)
            return

    v = [i + 1 if c == '1' else 0 for (i, c) in enumerate(s)]
    v[-1] = n

    last = n
    for i, x in reversed(list(enumerate(v))):
        if x != 0:
            v[i] = last
            last = x
        else:
            v[i] = last

    for i, x in enumerate(v[:-1]):
        print(i + 1, x)


if __name__ == '__main__':
    solve()

Solution (Python):
x = [c  for c in input()]

n = len(x)
ret=[]
for i in range(n-1):
    ret.append([0,0])

if x[n-1] == "1":
    print (-1)
elif x[0] == "0":
    print (-1)
else:
    flg = 1
    for i in range(int((n-1)/2)):
        if x[i] != x[n-1-i-1]:
            flg = 0
    if flg == 0:
        print (-1)
    else:
        a=1
        b=n
        for i in range(int((n-2)/2)):
            if x[i] == "1":
                ret[i] = [a,i+2]
                ret[n-i-2] = [b,n-i-2+1]
                a=i+2
                b=n-i-2+1
            else:
                ret[i] = [a,i+2]
                ret[n-i-2] = [b,n-i-2+1]
                
        if n % 2 == 1:
            i = int((n-3)/2)
            if x[i] == "1":
                ret[i] = [a,i+2]
                ret[n-i-2] = [b,n-i-2+1]
            else:
                tmp = b
                for j in range(i):
                    if ret[n-j-2][1] == b:
                        ret[n-j-2][1] = a
                    if ret[n-j-2][0] == b:
                        ret[n-j-2][0] = a
                ret[i] = [a,i+2]
                ret[n-i-2] = [a,tmp]
        else:
            i = int(n/2)-1
            if x[i] == "1":
                ret[i] = [a,b]
            else:
                tmp = b
                for j in range(i):
                    if ret[n-j-2][1] == b:
                        ret[n-j-2][1] = a
                    if ret[n-j-2][0] == b:
                        ret[n-j-2][0] = a
                ret[i] = [a,b]
                
        
        for i in range(n-1):
            print ("{0} {1}".format(ret[i][0], ret[i][1]))

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    s = f.read_str()
    n = len(s)
    a = map(int, list(s))

    if a[-1] == 1: return -1
    if a[0] == 0: return -1

    va = [n]
    for i in xrange(n/2):
        if a[i] != a[-i-2]: return -1
        if a[i] == 1:
            vv = va.pop()
            va.extend([vv-(n-(i+1)), n-(i+1)])

    ans = ["%d %d"%(i+1, i+2) for i in xrange(len(va)-1)]
    c = len(va) + 1
    for i, v in enumerate(va):
        for _ in xrange(v-1):
            ans.append("%d %d"%(i+1, c))
            c += 1

    return "\n".join(ans)


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):



ss=input()
ans=0

if ss[-1]=="1":
    ans=-1
s=ss[:-1]

gans=[]

c=1
for i in range(len(s)):
    if i==0 and s[i]=="0":
        ans=-1
        break
    if s[i] != s[len(s)-i-1]:
        ans=-1
        break
    
    if s[i]=="1":
        gans.append([c, i+2])
        c=i+2
    else:
        gans.append([i+2,c])


if ans==-1:
    print(ans)
else:
    for i in gans:
        print(*i)

Solution (Python):
vs = [int(i) for i in input().strip()]
n = (len(vs) - 2)//2
def main(vs):
    if vs[0] != 1:
        print(-1)
        return -1
    if vs[-1] != 0:
        print(-1)
        return -1
    if vs[-2] != 1:
        print(-1)
        return -1
    for i in range(n):
        if vs[i+1] != vs[-2-i-1]:
            print(-1)
            return

    temp = 1
    for i in range(n+1 if len(vs) % 2 == 0 else n+2):
        print(1, temp+1)
        temp += 1
    temptemp = temp
    temp = 1
    for i in range(n):
        x = 1+n-i
        if vs[n-i] == 1:
            print(temptemp, temptemp+1)
            temp = temptemp
            temptemp += 1
        else:
            print(temp, temptemp+1) 
            temptemp += 1

main(vs)

Solution (Python):
S = input()
N = len(S)

if S[0] == "0" or S[-1] == "1":
    print(-1)
    exit()

D = {}
for i in range(N - 1):
    D[i + 1] = S[i]
for i in range(1, N):
    if D[i] != D[N - i]:
        print(-1)
        exit()


T = [[] for i in range(N)]

next = 1
mark = 0
for i in range(N):
    child = mark + 1
    if S[i] == "0":
        next += 1
    else:
        for n in range(next):
            T[mark].append(child)
            child += 1
        next = 1
        mark = child - 1

for i in range(N):
    for t in T[i]:
        print(i + 1, t + 1)

Solution (Python):


import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(S):
    N = len(S)

    if S[0] == '0' or S[-1] == '1':
        return None

    for i in range((N - 1) // 2):
        if S[i] != S[-2 - i]:
            return None

    mxsz = 1
    for i in range((N - 2) // 2):
        if S[i + 1] == '1':
            mxsz = i + 2

    G = []
    
    root = mxsz + 1
    croot = root

    for i in range(root - 1, 0, -1):
        G.append((croot, i))
        if S[i - 1] == '1':
            croot = i

    for i in range(mxsz + 2, N + 1):
        G.append((root, i))

    return G


def main():
    ans = solve(inp())
    if ans is None:
        print('-1')
        return
    for (p, q) in ans:
        print(p, q)


if __name__ == '__main__':
    main()

Solution (Python):
s = raw_input()
n=len(s)
pos=True
if s[0]!="1" or s[-1]!="0":
    pos=False
else:
    if n%2==0:
        for i in range(n/2 - 1):
            if s[i]!=s[n-i-2]:
                pos=False
                break
    else:
        for i in range((n-1)/2):
            if s[i]!=s[n-i-2]:
                pos=False

res_list = []
if pos==False:
    print -1
else:
    rep=1
    if n%2==0:
        for i in range(n/2):
            if s[i]=="1":
                res_list.append([rep,i+2])
                rep=i+2
            else:
                res_list.append([rep,i+2])
        for i in range(n/2-1):
            res_list.append([rep,i+n/2+2])
    else:
        for i in range((n-1)/2):
            if s[i]=="1":
                res_list.append([rep,i+2])
                rep=i+2
            else:
                res_list.append([rep,i+2])
        for i in range((n-1)/2):
            res_list.append([rep,i+(n-1)/2+2])

    for res in res_list:
        print str(res[0]) + " " + str(res[1])

Solution (Python):
def main():
	s = input()
	if s[-1] == "1" or s[0] == "0":
		print(-1)
		return
	if s[0:-1][::-1] != s[:-1]:
		print(-1)
		return
	temp = 1
	init = []
	for i in range(1,int((len(s)+1)/2)):
		if s[i] == "1":
			for j in range(temp+1, i+2):
				print(temp, j, sep=" ")
			init += [temp]
			temp = i+2
	if temp != len(s):
		for j in range(temp+1, len(s)+1):
			print(temp, j, sep=" ")
	init += [temp]
	for i in range(len(init)-1):
		print(init[i], init[i+1], sep=" ")
	

main()

Solution (Python):

s = list(input())
N = len(s)
res = True
if s[0] == "0" or s[N-1] == "1":
    res = False
for i in range(N-1):
    if s[i] != s[N-2-i]:
        res = False
if res == False:
    print(-1)
else:
    k = 1
    for i in range(N-1):
        if s[i] == "1":
            while k < i+1:
                print(str(k)+" "+str(i+1))
                k += 1
    while k < N:
        print(str(k)+" "+str(N))
        k += 1

Solution (Python):
ss = input()
n = len(ss)

if ss[0] == '0' or ss[-1] == '1':
    print(-1)
    exit()
else:
    for s1, s2 in zip(ss[:n//2], ss[n//2-1:-1][::-1]):

        if s1 != s2:
            print(-1)
            exit()

vMin, vMax = 1, n
iPrev = 0

for i, s in enumerate(ss, 1):
    if s == '0': continue


    print(vMin, vMin + 1)

    for j in range(i - iPrev - 1):
        print(vMin, vMax)
        vMax -= 1

    vMin += 1
    iPrev = i

Solution (Python):
S = input()
N = len(S)

if S[0] == '0' or S[-1] == '1':
    print(-1)
    exit()

mem = []
for i in range(N//2):
    if S[i] != S[-2-i]:
        print(-1)
        exit()
    if S[i] == '1':
        mem.append(i)

if len(mem)==0:
    print(-1)
    exit()

ans = []
for i in range(1,len(mem)+1):
    ans.append((i,i+1))

last_v = len(mem)+1

for i in range(mem[0]):
    last_v += 1
    ans.append((1,last_v))

for i,(a,b) in enumerate(zip(mem, mem[1:])):
    n = i+2
    k = b-a-1
    for _ in range(k):
        last_v += 1
        ans.append((n,last_v))

n = len(mem)+1
for _ in range(N):
    last_v += 1
    if last_v > N: break
    ans.append((n,last_v))

for row in ans:
    print(*row)

Solution (Python):
s = input()
n = len(s)
flg = 1
lis = []
if s[-1] == '1':
    print('-1')
    flg = 0
else:
    for i in range(n//2):
        if s[i] == s[n-2-i]:
            lis.append(int(s[i]))
        else:
            print('-1')
            flg = 0
            break
if flg ==1:
    if lis[0] == 0:
        print('-1')
    else:
        posl = []
        for i in range(1,len(lis)):
            pos = i+1
            if lis[i]==1:
                posl.append(pos)
        old = 1
        for pos in posl:
            for i in range(old,pos):
                print('{} {}'.format(i,pos))
            old=pos
        print(('{} {}'.format(old,old+1)))
        for i in range(old+2,n+1):
            print(('{} {}'.format(old+1,i)))

Solution (Python):
import sys
s=input()
N=len(s)
if s[-1]=='1':
    print(-1)
    sys.exit()
if s[0]=='0':
    print(-1)
    sys.exit()
t=s[:N-1]
t=t[::-1]
if s[:N-1]!=t:
    print(-1)
    sys.exit()
u=s[:N-1]
ans=[]
x=1
y=1
for i in range(N-1):
    if u[i]=='0':
        y+=1
        ans.append((x,y))
    else:
        y+=1
        ans.append((x,y))
        x=y
for x,y in ans:
    print(x,y)

Solution (Python):
import sys
s=input()

check=1
if s[-1]=="1":
    check=0

if s[0]=="0":
    check=0

n=len(s)
for i in range(n//2):
    if s[i]!=s[n-2-i]:
        check=0

if check==0:
    print(-1)
    sys.exit()


print(1,2)
next=2
for i in range(1,n-1):
    print(next,i+2)
    if s[i]=="1":
        next=i+2

Solution (Python):
S = input()
def is_asynmetric(S):
  for i in range(len(S) // 2):
    if S[i] != S[-(i + 2)]:
      return True
  else:
    return False
if S[0] != '1' or S[-2:] != '10':
  print(-1)
elif is_asynmetric(S):
  print(-1)
else:
  print('1 2')
  edge = 2
  for i, s in enumerate(S[1:-1], 3):
    print(edge, i)
    edge = edge if s == '0' else i

Solution (Python):
S=input()
N=len(S)
if S[-1]=="1":
    print(-1)
    exit()
if S[0]=="0":
    print(-1)
    exit()
if S[-2]=="0":
    print(-1)
    exit()
for i in range(N-1):
    if S[i]!=S[N-2-i]:
        print(-1)
        exit()
ans=[]
nowzero=0
for i in range(N):
    if S[i]=="0":
        break
    nowzero+=1
if nowzero==N-1:
    for i in range(1,N):
        print(i,i+1)
    exit()
ans.append((1,2))
for i in range(N-2):
    if S[i]=="1":
        if i!=N-2 and S[i+1]=="0":
            nowzero=i+2
        ans.append((i+2,i+3))
    else:
        ans.append((nowzero,i+3))
for line in ans:
    print(line[0],line[1])

Solution (Python):
import sys

s = input()
n = len(s)
if s[0] == "0" or s[-1] == "1":
	print(-1)
	sys.exit()

possible = []
for i in range(n // 2):
	if s[i] != s[n - i - 2]:
		print(-1)
		sys.exit()

	if i > 0 and s[i] == "1":
		possible.append(i+1)


l = len(possible)

edges = []

cnt = 0
for i in range(l):
	for j in range(cnt + 1, possible[i]):
		edges.append([j, possible[i]])
	if i != l - 1:
		edges.append([possible[i], possible[i+1]])
	else:
		edges.append([possible[i], possible[i] + 1])

	cnt = possible[i]

for i in range(cnt + 2, n + 1):
	edges.append([cnt + 1, i])

for e in edges:
	print(*e)

Solution (Python):
s=input()
n=len(s)
flag=False
for i in range(n//2):
    if s[i]!=s[-i-2]:
        flag=True
        break
if flag or s[0]=="0" or s[-1]=="1":
    print(-1)
elif n==2:
    print("2 1")
elif n==3:
    print("2 1")
    print("3 2")
else:
    print("2 1")
    head=2
    for i in range(3,n//2+2):
        print(str(i)+" "+str(head))
        if s[i-2]=="1":
            head=i
    i+=1
    while i<=n:
        print(str(i)+" "+str(head))
        i+=1

Solution (Python):
s = raw_input()
n = len(s)
s = "0"+s

if s[1]=="0":
  print -1
  exit(0)
for i in range(1,n+1):
  if s[i]!=s[n-i]:
    print -1
    exit(0)

ans = [(0,1)]
p = 1
c = 2
for i in range(2,n):
  ans += [(p,c)]
  c += 1
  if s[i]!="0":
    p = c-1

for a in ans:
  print a[0]+1, a[1]+1

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

s = input()
n = len(s)

def valid(s):
  s = 'x' + s
  return (
    s[1] == '1' and
    s[n] == '0' and
    all(s[i] == s[n-i] for i in range(1, n))
  )

if not valid(s):
  print(-1); exit()

top = 1
for i in range(n-1):
  v = i + 2
  print(top, v)
  if s[i] == '1':
    top = v

Solution (Python):
s = input().strip()
n = len(s)
s = {i + 1 for i in range(n) if s[i] == '1'}

if n in s or 1 not in s or any(n - x not in s for x in s):
    print(-1)
else:
    s = sorted(s)
    c = 1
    e = []
    for i in range(1, len(s)):
        while c < s[i]:
            e.append((c, s[i]))
            c += 1
    e.append((c, n))
    e = [str(u) + ' ' + str(v) for u, v in e]
    print(*e, sep='\n')