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):
import sys
input = sys.stdin.readline

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        print(-1)
        exit()
    if S[N] == '1':
        print(-1)
        exit()
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            print(-1)
            exit()
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    for i in range(prev,N):
        graph.append('{} {}'.format(i,N))
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    print('\n'.join(graph))

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

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        print(-1)
        exit()
    if S[N] == '1':
        print(-1)
        exit()
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    for i in range(prev,N):
        graph.append('{} {}'.format(i,N))
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    print('\n'.join(graph))

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = '-' + sr()
N = len(S) - 1
def solve(S):
    if S[1] == '0':
        print(-1); exit()
    if S[N] == '1':
        print(-1); exit()
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            print(-1); exit()
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    for i in range(prev,N):
        graph.append('{} {}'.format(i,N))
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    print('\n'.join(graph))

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = '-' + sr()
N = len(S) - 1
def solve(S):
    if S[1] == '0':
        return None
    if S[N] == '1':
        return None
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    for i in range(prev,N):
        graph.append('{} {}'.format(i,N))
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    print('\n'.join(graph))

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = list(sr())
N = len(S)
if S[-1] == '1' or S[0] == '0' or S[:-1] != S[:-1][::-1]:
    print(-1); exit()
S = ['-'] + S

def solve(S):
    prev = 1
    graph = []
    for i in range(1, N//2 + 1):
        if S[i] == '0':
            continue
        for x in range(prev, i):
            print(x, i)
        prev = i
    for x in range(prev, N):
        print(x, N)

graph = solve(S)

Solution (Python):
s=list(input())
n=len(s)
if s[0] != "1" or s[-1]=="1" or s[:(n-1)//2] != s[n-2:n//2-1:-1]:
  print(-1)
  exit()
chain = [1]
ans = []
s[-1] = "1"
for i in range(1,n):
  if s[i] == "1":
    chain.append(i+1)
    ans.append((chain[-2],chain[-1]))
c = len(chain)
for i in range(1,c):
  for j in range(chain[i-1]+1,chain[i]):
    ans.append((j,chain[i]))
for edge in ans:
  print(*edge)

Solution (Python):
from bisect import bisect_right
s = list(map(int,list(input())))
s.insert(0,-1)
n = len(s)-1
flag = 0
if s[n]==1 or s[1]==0 or s[n-1]==0:
    flag = 1
else:
    for i in range(2,n-1):
        if s[i]!=s[n-i]:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    print(n,n-1)
    A = [1,n-1]
    cur = 1
    for i in range(2,n-1):
        if s[i]==1:
            print(cur,i)
            cur = i
            A.append(i)
    print(cur,n-1)
    A = sorted(A)
    for i in range(2,n-1):
        if s[i]==0:
            ind = bisect_right(A,i)
            print(i,A[ind])

Solution (Python):
def main():
    s=input()
    n=len(s)
    res = []
    if s[0]=="0" or s[-1] == "1":
        print(-1)
        return 1
    m=n//2
    t=m
    for i in range(m,0,-1):
        if s[i-1] != s[n-i-1]:
            print(-1)
            return 1
        if i == m:
            if s[i-1]=="1":
                res.append([m,m+1])
                for j in range(m+2,n+1):
                    res.append([m+1,j])
            else:
                for j in range(m+1,n+1):
                    res.append([m,j])
        else:
            if s[i-1]=="1":
                res.append([t,i])
                t=i
            else:
                res.append([t,i])
    for sres in res:
        print(" ".join(map(str, sres)))


main()

Solution (Python):
import sys

s=list(map(int,list(input())))
n=len(s)
if s[0]==0 or s[-1]==1:
    print(-1)
    sys.exit()
for i in range(n//2):
    if s[i]==s[n-2-i]:
        continue
    else:
        print(-1)
        sys.exit()
ans=[[1,2]]
last_edge=2
for i in range(3,n+1):
    ans.append([last_edge,i])
    if s[i-2]==1:
        last_edge=i
for u in ans:
    print(*u)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    N = len(S)
    if S[N-1] == '1':
        print(-1)
        return -1

    if S[0] != '1':
        print(-1)
        return -1

    if S[N-2] != '1':
        print(-1)
        return -1


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

    p = [N]
    for i in range(N, 0, -1):
        if S[i-1] == '1':
            p.append(i)
        else:
            p.append(p[-1])
    p.reverse()
    e = []
    for i in range(1, N):
        e.append((i, p[i]))

    for u, v in e:
        print(u, v)


def main():
    S = read_str()
    (slv(S))


if __name__ == '__main__':
    main()

Solution (Python):
s = '0'
s += input()


def isPara(string, l, r):
    while l <= r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True


def solve():
    N = len(s)-1
    if s[N] == '1' or s[1] == '0':
        print(-1)
        return
    if isPara(s, 1, N-1) == False:
        print(-1)
        return
    root = 1
    for i in range(2, N+1):
        print(str(root) + ' ' + str(i))
        if s[i-1] == '1':
            root = i


solve()

Solution (Python):
s = '0'
s += input()


def isPara(string, l, r):
    while l <= r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True


def solve():
    N = len(s)-1
    if s[N] == '1' or s[1] == '0':
        print(-1)
        return
    if isPara(s, 1, N-1) == False:
        print(-1)
        return
    sz = 1
    while sz < N:
        if(s[sz] == '1'):
            sz += 1
        else:
            break
    sz -= 1
    
    now = 1
    for i in range(2, N+1):
        print(str(now) + ' ' + str(i))
        if(s[i-1] == '1'):
            now = i


solve()

Solution (Python):
s = input()

N = len(s)

flag=True
if s[N-1]=='1':
        flag=False
if s[0]=='0' or s[N-2]=='0':
        flag=False


for i in range(N//2):
        if s[i]!=s[N-i-2]:
                flag=False
                break

if flag:
        ans = []
        prev = 0
        for i in range(N//2):
                if s[i]=='1':
                        for j in range(prev,i):
                                ans.append([i+1,j+1])
                        prev = i
        
        for i in range(prev,N-1):
                ans.append([N,i+1])
        
        for a in ans:
                print(*a)
else:
        print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    S=[None]+list(map(int,input()))
    n=len(S)-1

    
    if(not (S[1]==1 and S[n-1]==1)):
        print(-1)
        return
    if(S[n]==1):
        print(-1)
        return
    if(any(S[i]!=S[n-i] for i in range(1,n-1))):
        print(-1)
        return

    v=1
    nv=2
    for i in range(n-1,0,-1):
        print(v,nv)
        nv+=1
        if(S[i]==1): v=nv-1
resolve()

Solution (Python):
S = input()
T = S[:-1]

if S[0] == "0" or S[-1] == '1' or T != T[::-1]:
    print(-1)
    quit()

u = 1
for v in range(2, len(S) + 1):
   print(u, v)
   if S[v - 2] == '1':
       u = v

Solution (Python):
def main():
    s=input()
    n=len(s)
    if s[n-1]=="1" or s[0]=="0":
        print(-1)
        return 0
    for i in range(n//2):
        if s[i]!=s[n-i-2]:
            print(-1)
            return 0
    t=[]
    now=1
    for i in range(n//2-1):
        t.append([now,i+2])
        if s[i]=="1":
            now=i+2
    t2=[[i+n//2,j+n//2] for i,j in t]
    if s[n//2-1]=="1":
        t.append([now,now+n//2])
    else:
        for i in range(len(t2)):
            if t2[i][0]==now+n//2:
                t2[i][0]=now
            if t2[i][1]==now+n//2:
                t2[i][1]=now
        t.append([now,now+n//2])
    if n%2==1:
        t.append([now,n])
    t+=t2
    for i,j in t:
        print(i,j)
main()

Solution (Python):

from collections import defaultdict


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


def main():
	s = list(input())
	N = len(s)
	judge = "Yes"
	if s[0] == "0":
		judge = "No"
	if s[N - 1] == "1":
		judge = "No"
	for i in range(N - 2):
		if s[i] != s[N - 2 - i]:
			judge = "No"
	if judge == "No":
		print(-1)
		return

	c = 1
	d = N
	for i in range(N - 1):
		if s[i] == "1":
			print(c, c + 1)
			c += 1
		else:
			print(c, d)
			d -= 1

if __name__ == '__main__':
	main()

Solution (Python):
s = [int(i) for i in input()]
    
if s[0] == 0 or s[-1] == 1 :
    print(-1)
    
else :
    s.pop()
    if s != s[::-1] :
        print(-1)
        
    else :
        org = 1
        for i in range((len(s) + 1) // 2) :
            if s[i] == 1 :
                for j in range(org + 1, i + 3) :
                    print(org, j)
                org = i + 2
        for i in range(org + 1, len(s) + 2) :
            print(org, i)

Solution (Python):
import sys
S = input()
N = len(S)
ss = S[:N-1]
if S[-1] == '1' or ss != ss[::-1] or S[0] == '0':
    print(-1)
    sys.exit()
tree = []
cnt = 0
for s in ss:
    if s == '1':
        tree.append(cnt)
        cnt = 0
    else:
        cnt += 1
ans = []
now = 1
for c in tree:
    for i in range(c):
        ans.append((now, now+i+1))
    ans.append((now, now+c+1))
    now = now+c+1
for a, b in ans:
    print(a, b)

Solution (Python):
import sys

s = input()

num = len(s)

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

s = s[:-1]

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

lis = []
ans = []

for i in range(num-1):

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



now = 1
for i in range(len(lis)):

    while now < lis[i]:
        ans.append([now,lis[i]])
        now += 1

    if i != len(lis)-1:
        ans.append([lis[i],lis[i+1]])
        now += 1

ans.append([num-1,num])


for i in ans:
    print (i[0],i[1])

Solution (Python):
S = input()
N = len(S)
S = '0' + S
if S[:2] == '01' and S == S[::-1]:
    before = 1
    for i in range(2, N + 1):
        print(before, i)
        if S[i - 1] == '1' and i < (N + 1) // 2 + 2:
            before = i
else:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
s = list(map(int, list(input())[: -1]))
if s[0] == 0 or s[-1] == 1:
  print(-1)
  exit(0)
n = len(s)
for i in range(n - 1):
  if s[i] != s[-2 - i]:
    print(-1)
    exit(0)
res = []
temp = []
s[-1] = 1
for i in range(n):
  if s[i] == 0 or i == 0:
    temp.append(i + 1)
  else:
    if len(res):
      p = res[-1][0]
      res.append((i + 1, p))
    if len(temp):
      while len(temp):
        res.append((i + 1, temp.pop()))
for _ in range(len(res)):
  print(*res.pop())

Solution (Python):
s = input()
n = len(s)
if s[0] == '0':
    print(-1)
    exit(0)
if s[-1] == '1':
    print(-1)
    exit(0)
for i in range((n - 1) // 2):
    if s[i] != s[n - i - 2]:
        print(-1)
        exit(0)
p = 1
t = 2
i = n - 2
while i >= 0:
    print(p, t)
    if s[i] == '1':
        p = t
    t += 1
    i -= 1

Solution (Python):
S = [int(a) for a in list(input())]
L = len(S)

ok = True
if S[L-1] == 1 or S[0] == 0 or S[L-2] == 0:
    ok = False
for i in range(L-1):
    if S[i] != S[L-2-i]:
        ok = False

if not ok:
    print(-1)
else:
    graph = []
    p = 1
    go = True
    for i in range(1, L):
        if i <= L//2:
            graph.append((p, i+1))
            if go:
                p = i+1
            if S[i] == 1:            
                go = True
            else:
                go = False
        else:
            graph.append((p, i+1))
    
    for a, b in graph:
        print(a, b)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import deque

def main():
    s = input().strip()
    if s[-1] == '1' or s[0] == '0':
        print(-1)
    else:
        edges = deque([])
        for i in range(len(s)-1):
            if s[i] != s[len(s)-i-2]:
                print(-1)
                return
            elif s[i] == '1':
                edges.append(i)
        edges.append(len(s)-1)
        for i in range(len(s)-1):
            if edges[0] == i:
                edges.popleft()
            print(i+1, edges[0]+1)


if __name__ == '__main__':
    main()

Solution (Python):
A=list(input())
N=len(A)

if A[-1]=="1":
    print(-1)
elif A[0]!="1" or A[-2]!="1":
    print(-1)
else:
    for i in range(N-1):
        if A[i]!=A[N-2-i]:
            print(-1)
            exit()
    X=1
    Y=0
    
    for i in range(N-1):
        if A[i]=="1":
            print(Y+1,X+1)
            Y=X
            X+=1
        else:
            print(X+1,Y+1)
            X+=1

Solution (Python):
import bisect
s = input()
if s[-1] == "1" or s[0] == "0":
    print(-1)
    exit()

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

sd = s[:-1] + '1'
plist = [i for i, v in enumerate(sd) if v == '1']

for i,v in enumerate(s[:-1]):
    r = bisect.bisect(plist,i)
    print(i+1,plist[r] + 1)

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

Solution (Python):
s = list(input())
n = len(s)

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

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

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

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

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

for s, t in zip(S[: N - 1], S[:: -1][1:]):
    if s != t:
        print('-1')
        exit()

now = 1
branch = N
ans = []
for s in S[: N - 1]:
    if s == '1':
        ans.append('{} {}'.format(now, now + 1))
        now += 1
    else:
        ans.append('{} {}'.format(now, branch))
        branch -= 1

print(*ans, sep='\n')

Solution (Python):
s=input()
slen=len(s)-1
slen2=(len(s)-1)//2
iswitch=0
for i in range(slen2):
    if s[i]!=s[slen-i-1]:
        iswitch=1

if s[-1]=='1' or s[0]=='0':
    iswitch=1

if iswitch==1:
    print(-1)
else:
    if slen==1:
        print("1 1")
    elif slen==2:
        print("1 2")
        print("1 3")
    else:
        if True:
            henlist=[]
            mae=1
            jswitch=0
            for i in range(slen):
                now=i+2
                if jswitch==0:
                    if s[now-1]=='1':
                        for i in range(now-mae):
                            henlist.append([mae+i, now])
                        mae=now
                        if now>(len(s))//2:
                            jswitch=1
                    else:
                        pass
                else:
                    henlist.append([mae, now])
        for hl in henlist:
            print(hl[0], hl[1])

Solution (Python):
from collections import deque
s = list(input())
n = len(s)

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

s[n-1] = '1'

one =deque([])

for i in range(n):
    if s[i] == '1':
        one.append(i)

for i in range(n-1):
    if s[i] == '0':
        print(i+1,one[0]+1)
    else:
        a = one.popleft()
        print(a+1,one[0]+1)

Solution (Python):
def main():
    S = input()
    N = len(S)
    ok = True
    if S[0] == "0" or S[N-1] == "1":
        ok = False
    for i in range(N-1):
        if S[i] != S[N-2-i]:
            ok = False
    if not ok:
        print(-1)
        return
    prev = 1
    for i in range(2, N+1):
        print(prev, i)
        if S[i-2] == "1":
            prev = i


if __name__ == "__main__":
    main()

Solution (Python):
s = input()

if s[-1]=='1':
    print(-1)
    exit()
if s[0]=='0':
    print(-1)
    exit()
for i in range(len(s)//2):
    if s[i]!=s[-i-2]:
        print(-1)
        exit()

print(1,2)
top = 2

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


s = S()


if s[0] == '0' or s[-1] == '1' or s[:-1] != s[:-1][::-1]:
    print(-1)
else:
    n = len(s)
    s = s[:-1]
    now_point = 1
    for nxt_point in range(len(s)):
        print(now_point, nxt_point+2)
        if s[nxt_point] == '1':
            now_point = nxt_point+2

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = sys.stdin.readline().rstrip()


def solve(S: str):
    if S[-1] == '1':
        return None
    S = S[:-1]
    if S[::-1] != S:
        return None
    if S[0] == '0':
        return None
    ret = [(1, 2)]
    v = 2
    for i in range(1, (len(S) + 1) // 2):
        ret.append((v, i + 2))
        if S[i] == '1':
            v = i + 2
    for i in range((len(S) + 1) // 2, len(S)):
        ret.append((v, i + 2))

    return ret


ans = solve(S)
if ans:
    for r in ans:
        print(*r)
else:
    print(-1)

Solution (Python):

s = input()
len_s = len(s)

if s[-1] == "1":
	print(-1)
	exit()
for i in range((len_s - 1)//2):
	if s[i] != s[len_s - 2 - i]:
		print(-1)
		exit()
if s[0] != '1':
	print(-1)
	exit()

num = 1
for i in range(len_s - 1):
	if s[i] == '1':
		print('{0} {1}'.format(num, i + 2))
		num = i + 2
	else:
		print('{0} {1}'.format(num, i + 2))

Solution (Python):
s = input().rstrip()
n = len(s)


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

for fs, bs in zip(s[:-1], s[:-1][::-1]):
    if fs != bs:
        print(-1)
        exit()

made = set()
node_num = 0
base = 0
for i, ch in enumerate(s[:-1]):
    if ch == "1" and i+1 not in made:
        node_num += 1
        print(node_num + 1, base + 1)
        base = node_num
        made.add(i+1)
        made.add(n-i-1)
    else:
        node_num += 1
        print(base + 1, node_num + 1)

Solution (Python):
s = input()

cnt = 0


if s[-1] == "1" or s[0] == "0":
    print(-1)
    exit()
    
li = []
for i in range(1, len(s) // 2):
    if s[i] != s[-i-2]:
        print(-1)
        exit()
    if s[i] == "1":
        li.append(i + 1)
        
tree = []
j = 1
for _ in range(len(li)):
    tree.append((j, j + 1))
    j += 1
li.append(len(s))

cnt = 0
for i in range(len(li)):
    cnt += 1
    while cnt < li[i]:
        tree.append((i + 1, j + 1))
        j += 1
        cnt += 1

for edge in tree:
    print(*edge)

Solution (Python):
S = input()

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

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

print("1 2")
current_root = 1
for i in range(1, len(S)-1):
    print("{:d} {:d}".format(i+2, current_root+1))
    if i << len(S)//2 and S[i] == "1":
        current_root = i+1

Solution (Python):
s = input()

S = '0' + s
N = len(s)



def f():
    res = []
    r = 1
    C = []
    for i in range(2, N + 1):
        if S[i] == '0':
            C.append(i)
        else:
            res.append((r, i))
            r = i
            for c in C:
                res.append((r, c))
            C = []
    for c in C:
        res.append((r, c))
    return res


ans = (
    '-1' if S[1] == '0' or S[N] == '1' or any(
        S[i] != S[N - i]
        for i in range(1, N)
    ) else
    '\n'.join(
        '{} {}'.format(u, v)
        for u, v in f()
    )
)

print(ans)

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

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        return None
    if S[N] == '1':
        return None
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    graph += ['{} {}'.format(i,N) for i in range(prev,N)]
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    print('\n'.join(graph))

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

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        return None
    if S[N] == '1':
        return None
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    for i in range(prev,N):
        graph.append('{} {}'.format(i,N))
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    print('\n'.join(graph))

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

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        return None
    if S[N] == '1':
        return None
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append((i,n))
        prev = n
    for i in range(prev,N):
        graph.append((i,N))
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    for x,y in graph:
        print(x,y)

Solution (Python):
from sys import exit
def muri():
    print(-1)
    exit()

L = list(map(int, input()))
N = len(L)
if L.pop():
    muri()
if not L[0]:
    muri()
if L != L[::-1]:
    muri()
if N == 2:
    print(1, 2)
    exit()

Ans = []
M = [i for i, l in enumerate(L, 1) if l] 
K = [0] + [m2 - m1 - 1 for m1, m2 in zip(M, M[1:])] + [0]
p = 1
for _ in range(len(M)):
    Ans.append((p, p+1))
    p += 1
p += 1
for j, k in enumerate(K, 1):
    for _ in range(k):
        Ans.append((j, p))
        p += 1

for a in Ans:
    print(*a)

Solution (Python):
s = input()
N = len(s)
if s[0]=="0" or s[-1]=="1":
    print(-1)
    exit()
Ans = []
q = [0]
for i in range(1, N//2):
    c, cr = s[i], s[-2-i]
    if c!=cr:
        print(-1)
        exit()
    else:
        if c=="1":
            for u in q:
                Ans.append([u, i])
            q = [i]
        else:
            q.append(i)
i = N//2
if N%2==1:
    for u in q:
        Ans.append([u, i])
    for ans in Ans:
        print(ans[0]+1, ans[1]+1)
        print(N-ans[0], N-ans[1])
else:
    if len(q)==1:
        print(i, i+1)
        for ans in Ans:
            print(ans[0] + 1, ans[1] + 1)
            print(N - ans[0], N - ans[1])
    else:
        v = q.pop()
        for u in q:
            print(v+1, u+1)
            print(v+1, N-u)
        print(i, i+1)
        for ans in Ans:
            print(ans[0] + 1, ans[1] + 1)
            print(N - ans[0], N - ans[1])

Solution (Python):
s = input()

n = len(s)

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




ss = []

for i in range(n-1,-1,-1):
    if s[i] == '1':
        ss.append(i+1)


now_no = 1
now_siz = n
for siz in ss:
    others = now_siz - siz - 1
    for i in range(1,others+1):
        print(now_no,now_no+i)
    print(now_no,now_no+others+1)
    now_no += others+1
    now_siz = siz

Solution (Python):
import math

s = input()

N = len(s)
s = "
possible = 1
if s[-1] == "1" or s[1] == "0":
  possible = 0
for i in range(1,math.floor(N/2)):
  if s[i] != s[N - i]:
    possible = 0

if not possible:
  print(-1)
elif N == 2:
  if s[1] == "1" and s[2] == "0":
    print(1, 2)
  else:
    print(-1)
elif N == 3:
  if s[1] == "1" and s[2] == "1":
    print(1,2)
    print(2,3)
  else:
    print(-1)
else:
  destination = [1] * (N+1)
  dest_change = [0] * (N+1)
  root = 2
  max_bit = math.floor(N/2)
  for i in range(max_bit, -1, -1):
    if s[i] == "1":
      
      dest_change[root + 1] = dest_change[root + 1] + 1
      dest_change[root + i] = dest_change[root + i] - 1
      root += 1
  for i in range(1,N+1):
    destination[i] = destination[i - 1] + dest_change[i]
  for i in range(2,N+1):
    print(i, destination[i])

Solution (Python):
def check_str(s):
    n = len(s) - 1
    if (s[1] != 1) or (s[-1] != 0):
        return False
    else:
        for i in range(1, n / 2):
            if s[i] != s[n - i]:
                return False
    return True

def solve():
    s = [int(_) for _ in raw_input()]
    s.insert(0,0)
    if not check_str(s):
        print '-1'
        return
    sub = []
    for i in range(len(s)):
        if s[i] == 1:
            sub.append(i)
    
    
    body_leng = len(sub) + 1
    for i in range(1, body_leng):
        print str(i) + ' ' + str(i+1)
    
    cnt = body_leng
    for i in range(1, body_leng - 1):
        num_legs = sub[i] - sub[i-1] - 1
        for j in range(cnt + 1, cnt + num_legs + 1):
            print str(i+1) + ' ' + str(j)
        cnt += num_legs

if __name__ == '__main__':
    solve()

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

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

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

path = {1:[v for v in range(2, n+1)]}

ans = []
u_cur, v_cur = 1, 2
n_prev = 0
for i in range(1, n//2):
    if s[i] == '1':
        for _ in range(i-n_prev):
            ans.append((u_cur, v_cur))
            v_cur += 1
        ans.append((v_cur, u_cur))
        u_cur, v_cur = v_cur, v_cur+1
        n_prev = i+1
for v in range(v_cur, n+1):
    ans.append((v_cur-1, v))
for a in ans:
    print(*a)

Solution (Python):
s = list(input())

n = len(s)

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

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

s[n-1] = '1'

i = 0
while i < n-1:
    p = -1
    for j in range(i+1, n):
        if s[j] == '1':
            p = j
            break
    for k in range(i, p):
        print(k+1, p+1)
    i = p

Solution (Python):
inp=[int(x) for x in list(input())]
length=len(inp)
x,y=(0,length-2)

if (not inp[0]==inp[length-2]==1) or inp[length-1]==1:
  print(-1)
  exit()

while x<y:
  if inp[x]!=inp[y]:
    print(-1)
    exit()
  else:
    x+=1
    y-=1

now=1
num=1
if length<=4:
  for x in inp:
    num+=1
    if x:
      print (now,num)
      now=num
    else:
      print (now,num)
    if num==length:
      break
else:
  for x in inp:
    num+=1
    if x:
      print (now,num)
      if num!=length-1:
        now=num
    else:
      print (now,num)
    if num==length:
      break

Solution (Python):
s = input()

flag = False
if s[0] == "0": flag = True
if s[-1] == "1": flag = True

N = len(s) // 2 + len(s) % 2
for i in range(N):
  if s[i] != s[-2 - i]:
    flag = True

if flag:
  print("-1")
  exit()

re = 1
for i in range(1, len(s)):
  print(re, i + 1)
  if s[i - 1] == "1":
    re = i + 1