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.



Sample input:
1111


Sample output:
-1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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()

# 1頂点に全部ついた状態から始める
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
  # now の木から子をi個取り出して繋げる
  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)

Submission status: Accepted

Solution code:
#!/usr/bin/env 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()

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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 #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

ss=input()
ans=0

if ss[-1]=="1":
    ans=-1
s=ss[:-1]
#print(s)
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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 = []
    # print(mxsz)
    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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
# E
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

Submission status: Accepted

Solution code:
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]):
#        print(s1, s2)
        if s1 != s2:
            print(-1)
            exit()

vMin, vMax = 1, n
iPrev = 0
#for i, s in enumerate(ss[:n//2], 1):
for i, s in enumerate(ss, 1):
    if s == '0': continue
#    print(i, ':', vMin)
#    if vMin > 1:
    print(vMin, vMin + 1)

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

    vMin += 1
    iPrev = i

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

#print(possible)
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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')

Submission status: Runtime Error

Solution code:
s=list(map(int,list(input())))
# s[0]=1,s[-1]=0,s[k]=s[n-k-1]は必要
def main(s):
  n=len(s)
  if s[0]!=1 or s[-1]!=0:return [-1]
  for k in range(n//2-1):
    if s[k]!=s[n-k-2]:return [-1]
  uv=[(1,2)]
  t=2
  i=3
  for x in s[1:-1]:
    uv.append((t,i))
    if x==1:
      t=i
    i+=1
  return uv
for x in main(s):
  print(*x,sep=' ')

Submission status: Runtime Error

Solution code:
def main():
    S = list(input())

    N = len(S)

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

    lst = []
    for i in range((N - 1) // 2):
        if S[i] != S[N - 2 - i]:
            print (-1)
            return 0
        if S[i] == '1':
            lst.append(i + 1)
    if N % 2 == 0 and S[N//2 - 1] == '1':
        lst.append(N//2)
    # print (lst)

    if lst[-1] * 2 != N:
        center = lst[-1] + 1
        for x in range(lst[-1] * 2 + 2, N + 1):
            print (center, x)

        before = 1
        n = lst[-1] * 2 + 2
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, center)
        print (n - tmp, center)

    if lst[-1] * 2 == N:
        before = 1
        n = lst[-1] * 2 + 1
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, n - tmp)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    S = list(input())

    N = len(S)

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

    lst = []
    for i in range((N - 1) // 2):
        if S[i] != S[N - 2 - i]:
            print (-1)
            return 0
        if S[i] == '1':
            lst.append(i + 1)
    if N % 2 == 0 and S[N//2 - 1] == '1':
        lst.append(N//2)
    # print (lst)

    if lst[-1] * 2 != N:
        center = lst[-1] + 1
        for x in range(lst[-1] * 2 + 2, N + 1):
            print (center, x)

        before = 1
        n = lst[-1] * 2 + 2
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, center)
        print (n - tmp, center)

    if lst[-1] * 2 == N:
        before = 1
        n = lst[-1] * 2 + 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, n - tmp)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    S = list(input())

    N = len(S)

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

    lst = []
    for i in range((N - 1) // 2):
        if S[i] != S[N - 2 - i]:
            print (-1)
            return 0
        if S[i] == '1':
            lst.append(i + 1)
    # print (lst)

    if lst[-1] * 2 != N:
        center = lst[-1] + 1
        for x in range(lst[-1] * 2 + 2, N + 1):
            print (center, x)

        before = 1
        n = lst[-1] * 2 + 2
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, center)
        print (n - tmp, center)

    if lst[-1] * 2 == N:
        before = 1
        n = lst[-1] * 2 + 2
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, n - tmp)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = list(input())
if S[-1] == '1':
    print (-1)
    exit()
if S[0] == '0':
    print (-1)
    exit(9)

N = len(S) - 1
n = (N + 1) // 2 #切り上げ

flag = True
tmp = -1
for i in range(n):
    if flag:
        if S[i] == S[N - 1 - i] == '1':
            tmp = i
        elif S[i] == S[N - 1 - i] == '0':
            flag = False
        else:
            print (-1)
            exit()
    else:
        if S[i] == S[N - 1 - i] == '0':
            continue
        else:
            print (-1)
            exit()

if tmp == 0:
    for k in range(N):
        print (1, k + 2)
    exit()

for i in range(tmp):
    print (i + 1, i + 2)
    print (N - i, N - i + 1)

print (i + 2, i + 3)
if N - i != i + 3:
    print (N - i, i + 3)
else:
    exit()

for j in range(i + 4, N - i):
    print (i + 3, j)

Submission status: Runtime Error

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
S=input()
if S[-1]=="1" or  S[0]=="0":
    print(-1)
    exit()
if S=="1010":
    print(1,2)
    print(1,3)
    print(1,4)
    exit()




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

odds=[]
even=[]
lst=[]
for i in range(2,length+1+(len(S)%2==0)):

    if S[i-1]=="1":
        if i%2==1:
            odds.append(i)
        else:
            even.append(i)

oddscount=0
p=1
pmax=2
usedlst=set()
for num in odds:
    lst.append([p,pmax])
    usedlst.add(p)
    usedlst.add(pmax)
    p=pmax
    for i in range(1,num-oddscount-1):
        lst.append([pmax,pmax+i])
        usedlst.add(pmax+i)
    pmax+=num-oddscount-2
    oddscount=num
oddsP=p
oddscount=0
if odds:
    p+=2
pmax=p+1

for num in even:
    lst.append([p,pmax])
    usedlst.add(p)
    usedlst.add(pmax)
    if num==2:
        p+=1
        pmax+=1

    elif num!=2:
        for i in range(1,num-oddscount-2):
            lst.append([pmax,pmax+i])
            usedlst.add(pmax+i)
        pmax+=num-oddscount-2
        oddscount+=num

evenP=lst[-1][0]
zenbuset=set([i for i in range(1,len(S)+1)])
if odds and even:

    D=[oddsP]+list(zenbuset-usedlst)+[evenP]
elif odds:


    D=[oddsP]+list(zenbuset-usedlst)
else:

    D=[evenP]+list(zenbuset-usedlst)
for i in range(1,len(D)):
    lst.append([D[i-1],D[i]])

for l in lst:
    print(" ".join(map(str,l)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
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

    comp = []
    e = []

    l = [1]
    r = [j for j in range(2, N+1)]
    u = l.pop()
    v = r.pop()
    e.append((u, v))
    heapq.heappush(comp, (len(l), (u, l)))
    heapq.heappush(comp, (len(r), (v, r)))
    for i in range(2, N//2+1):
        if S[i-1] == '0':
            continue
        else:
            c = 0
            while c < i:
                c, (u, chs) = heapq.heappop(comp)
                if c < i:
                    for v in chs:
                        e.append((u, v))

            l = chs[:i]
            if l:
                v = l.pop()
                e.append((u, v))
                heapq.heappush(comp, (len(l), (v, l)))

            r = chs[i:]
            if r:
                v = r.pop()
                e.append((u, v))
                heapq.heappush(comp, (len(r), (v, r)))

    while comp:
        _, (u, vs) = comp.pop()
        for v in vs:
            e.append((u, v))

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



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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
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

    comp = []
    e = []

    l = [1]
    r = [j for j in range(2, N+1)]
    u = l.pop()
    v = r.pop()
    e.append((u, v))
    heapq.heappush(comp, (len(l), (u, l)))
    heapq.heappush(comp, (len(r), (v, r)))
    for i in range(2, N//2+1):
        if S[i-1] == '0':
            continue
        else:
            c = 0
            while c < i:
                c, (u, chs) = heapq.heappop(comp)
                if c < i:
                    for v in chs:
                        e.append((u, v))

            l = chs[:i]
            v = l.pop()
            e.append((u, v))
            heapq.heappush(comp, (len(l), (v, l)))

            r = chs[i:]
            v = r.pop()
            e.append((u, v))
            heapq.heappush(comp, (len(r), (v, r)))

    while comp:
        _, (u, vs) = comp.pop()
        for v in vs:
            e.append((u, v))

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



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


if __name__ == '__main__':
    main()