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: Wrong Answer

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)))
    # error_print(N)
    for i in range(N//2, 1, -1):
        if S[i-1] == '0':
            continue
        else:
            # error_print('--------')
            # error_print(i)
            # for s, (u, vs) in comp:
            #     error_print(s)
            c = 0
            while c < i:
                c, (u, chs) = heapq.heappop(comp)
                # error_print(c, i, '---')
                if c < i:
                    for v in chs:
                        e.append((u, v))
            rem = c - i
            if rem > i:
                rem = i
            l = chs
            r = [l.pop() for _ in range(rem)]
            if l:
                v = l.pop()
                e.append((u, v))
                heapq.heappush(comp, (len(l), (v, l)))
            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))

    assert len(e) == N-1
    for u, v in e:
        print(u, v)



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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)))
    # error_print(N)
    for i in range(N//2, 1, -1):
        if S[i-1] == '0':
            continue
        else:
            # error_print('--------')
            # error_print(i)
            # for s, (u, vs) in comp:
            #     error_print(s)
            c = 0
            while c < i:
                c, (u, chs) = heapq.heappop(comp)
                # error_print(c, i, '---')
                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: Wrong Answer

Solution code:
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
    # a max chain of sz
    print("1 2")
    for i in range(2, 2 + sz-1):
        print(str(i) + ' ' + str(i+1))
    for i in range(2 + sz, 1+N):
        print('1 ' + str(i))


solve()

Submission status: Wrong Answer

Solution code:
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
    # a max chain of sz
    total = 1
    root = 1
    while total < N:
        start = total + 1
        now_size = min(sz, N - total)
        for i in range(now_size-1):
            print(str(start) + ' ' + str(start + 1))
            start += 1
        print(str(root) + " " + str(total + 1))
        total = start
        sz = 1

solve()

Submission status: Wrong Answer

Solution code:
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
    # a max chain of sz
    total = 1
    root = 1
    while total < N:
        start = total + 1
        now_size = min(sz, N - total)
        for i in range(now_size-1):
            print(str(start) + ' ' + str(start + 1))
            start += 1
        print(str(root) + " " + str(total + 1))
        total = start

solve()

Submission status: Wrong Answer

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

    # check
    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+=1
resolve()

Submission status: Wrong Answer

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

    # check
    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

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

Submission status: Wrong Answer

Solution code:
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(i + 1, j)
                org = i + 2
        for i in range(org + 1, len(s) + 2) :
            print(org, i)

Submission status: Wrong Answer

Solution code:
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 :
        pre = 1
        org = 1
        for i in range(1, (len(s) + 1) // 2) :
            if s[i] == 1 :
                for j in range(i + 1 - pre + 1) :
                    print(org, org + j + 1)
                org = org + i - pre + 2
                pre = i + 1
        for i in range(org + 1, len(s) + 2) :
            print(org, i)

Submission status: Wrong Answer

Solution code:
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 :
        pre = 0
        org = 1
        for i in range(1, (len(s) + 1) // 2) :
            if s[i] == 1 :
                for j in range(i + 1 - pre + 1) :
                    print(org, org + j + 1)
                org = org + i - pre + 2
                pre = i + 1
        for i in range(org + 1, len(s) + 2) :
            print(org, i)

Submission status: Wrong Answer

Solution code:
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 + 1:
            before = i
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import itertools
S = input()
N = len(S)
S = '0' + S
A = [[int(i), len(list(v))] for i, v in itertools.groupby(S)]
if len(A) in [3, 5] and A[0][0] == A[-1][0] == 0 and A[1][0] == A[-2][0] == A[
        0][1] == A[-1][1] == 1:
    if len(A) == 3:
        #一直線
        for i in range(1, N):
            print(i, i + 1)
        exit()
    elif len(A) == 5 and A[1][1] == A[-2][1]:
        #脚の長さの最大値がA[1][1]のstar graph
        M = A[1][1]
        Q, R = N // M, N % M
        #Q本の長さMの脚、1本の長さRの脚
        a = [[N] for _ in range(Q + 1)]
        for i in range(1, N):
            a[i % (Q + 1)] += [i]
        for b in a:
            for c, d in zip(b, b[1:]):
                print(c, d)
        exit()
print(-1)

Submission status: Wrong Answer

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

def main():
    s = input().strip()
    if s[-1] == '1':
        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()

Submission status: Wrong Answer

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

for i in range((len(s) - 1) // 2):
    # print(i,len(s)- i - 2)
    if s[i] != s[len(s) - i -2]:
        print(-1)
        exit()
tmp = 0
for i,v in enumerate(s):
    if i == 0:
        continue
    elif i == len(s):
        v = '1'
    if v == '0':
        print(tmp+1, i+1)
    else:
        print(tmp+1, i+1)
        tmp = i

Submission status: Wrong Answer

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

for i in range((len(s) - 1) // 2):
    # print(i,len(s)- i - 2)
    if s[i] != s[len(s) - i -2]:
        print(-1)
        exit()
print("---")
tmp = 0
for i,v in enumerate(s):
    if i == 0:
        continue
    if s == '0':
        print(tmp+1, i+1)
    else:
        print(tmp+1, i+1)
        tmp = i

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
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>slen//2:
                            jswitch=1
                    else:
                        pass
                else:
                    henlist.append([mae, now])
        for hl in henlist:
            print(hl[0], hl[1])

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    N = len(S)
    ok = True
    if 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()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    N = len(S)
    ok = True
    if S[N-1] == "1":
        ok = False
    for i in range((N-1)//2):
        if S[i] != S[N-i-2]:
            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()

Submission status: Wrong Answer

Solution code:
s = input().rstrip()
# 1st order must exist
if s[0] == 0 or s[-1] == 0:
    print(-1)
    exit()
# x and n-x must be same 
for fs, bs in zip(s[:-1], s[:-1][::-1]):
    if fs != bs:
        print(-1)
        exit()

n = len(s)
order = []
for i, ch in enumerate(s):
    if ch == "1":
        order.append(i + 1)
continuas = True
flat = 0
cluster = []
prev = 0
for item in order:
    if continuas:
        if item == prev + 1:
            prev = flat = item
            continue
        else:
            continuas = False
            if item < n - flat and item <= n // 2:
                cluster.append(item)
    else:
        if item < n - flat and item <= n // 2:
            cluster.append(item)
# print(flat, cluster)
# Not to run-out nodes
if flat + sum(cluster) + 1 > n:
    print(-1)
    exit()
# Construct
node_num = 0
for i in range(flat):
    print(node_num+1, node_num+2)
    node_num += 1
for item in cluster:
    base = node_num + 1
    print(1, base+1)
    node_num += 1
    for i in range(item - 1):
        print(base+1, node_num+2)
        node_num += 1
while node_num < n-1:
    print(1, node_num+2)
    node_num += 1

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

s = input()

N = len(s)
s = "#" + s
possible = 1
if s[-1] == "1":
  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)
  root = 2
  for i in range(math.floor(N/2), -1, -1):
    if s[i] == "1":
      destination = destination[:root+1] + [root]*(i-1) + destination[root+i:]
      root += 1
  for i in range(2,N+1):
    print(i, destination[i])

Submission status: Wrong Answer

Solution code:
import math

s = input()

N = len(s)
s = "#" + s
possible = 1
if s[-1] == "1":
  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)
else:
  destination = [1] * (N+1)
  root = 2
  for i in range(math.floor(N/2), -1, -1):
    if s[i] == "1":
      destination = destination[:root+1] + [root]*(i-1) + destination[root+i:]
      root += 1
  for i in range(2,N+1):
    print(i, destination[i])

Submission status: Wrong Answer

Solution code:
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)
    print sub
    ## Create tree caterpillar type
    ## body
    body_leng = len(sub) + 1
    for i in range(1, body_leng):
        print str(i) + ' ' + str(i+1)
    ## legs
    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()

Submission status: Wrong Answer

Solution code:
s = input()
if s[0]=='0' or s[-1]=='1':
    print(-1)
    exit()
for i in range(1,len(s)//2):
    if s[i-1]=='1' != s[len(s)-i-1]=='0':
        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)

Submission status: Wrong Answer

Solution code:
s = input()
if s[0]=='0' or s[-1]=='1':
    print(-1)
    exit()
for i in range(1,len(s)//2):
    if s[i-1]=='1' and s[len(s)-i-1]=='0':
        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)

Submission status: Wrong Answer

Solution code:
s = input()
if s[0]=='0' or s[-1]=='1':
    print(-1)
    exit()
for i in range(len(s)//2-1):
    if s[i]=='1' and s[len(s)-i-2]=='0':
        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)

Submission status: Wrong Answer

Solution code:
s = input()
if s[0]=='0' or s[-1]=='1':
    print(-1)
    exit()
for i in range(len(s)//2):
    if s[i]=='1' and s[len(s)-i-2]=='0':
        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)

Submission status: Wrong Answer

Solution code:
s = input()
if s[0]=='0' or s[-1]=='1':
    print(-1)
    exit()
for i in range(len(s)//2):
    if s[i]=='1' and s[len(s)-1-i]=='0':
        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)

Submission status: Wrong Answer

Solution code:
s = input()
if s[0]=='0' or s[-1]=='1':
    print(-1)
    exit()
for i in range(len(s)//2):
    if s[i]=='1' and s[-i-2]=='0':
        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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    v = LI()
    d = [defaultdict(int) for i in range(2)]
    for i in range(n):
        d[i%2][v[i]] += 1
    if len(d[0].keys()) == len(d[1].keys()) == 1:
        if d[0].keys() == d[1].keys():
            ans = n//2
        else:
            d = [list(d[i].values()) for i in range(2)]
            ans = sum(d[0])-max(d[0])+sum(d[1])-max(d[1])
    else:
        d = [sorted(list(d[i].items()),key = lambda x:-x[1]) for i in range(2)]
        if d[0][0][0] != d[1][0][0]:
            ans = -d[0][0][1]-d[1][0][1]
            for i in range(len(d[0])):
                ans += d[0][i][1]
            for i in range(len(d[1])):
                ans += d[1][i][1]
        else:
            ans = -d[0][0][1]-d[1][1][1]
            for i in range(len(d[0])):
                ans += d[0][i][1]
            for i in range(len(d[1])):
                ans += d[1][i][1]
            ans2 = -d[0][1][1]-d[1][0][1]
            for i in range(len(d[0])):
                ans2 += d[0][i][1]
            for i in range(len(d[1])):
                ans2 += d[1][i][1]
            ans = min(ans,ans2)
    print(ans)
#D
def D():
    return

#E
def E():
    s = list(map(int,S()))
    if s[-1] == 1:
        print(-1)
        quit()
    s.pop(-1)
    if s != s[::-1]:
        print(-1)
        quit()
    n = len(s)
    ans = [[1,i+2] for i in range(n)]
    s = s[:n//2+n%2]
    m = (n+1)//2
    k = 0
    for i in range(len(s)):
        k += s[i]
    if k == 0:
        print(-1)
        quit()
    if sorted(s,reverse = True) != s:
        print(-1)
        quit()
    for i in range(k-1):
        ans[i+1] = [i+2,ans[i+1][1]]
    for i, j in ans:
        print(i,j)


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    v = LI()
    d = [defaultdict(int) for i in range(2)]
    for i in range(n):
        d[i%2][v[i]] += 1
    if len(d[0].keys()) == len(d[1].keys()) == 1:
        if d[0].keys() == d[1].keys():
            ans = n//2
        else:
            d = [list(d[i].values()) for i in range(2)]
            ans = sum(d[0])-max(d[0])+sum(d[1])-max(d[1])
    else:
        d = [sorted(list(d[i].items()),key = lambda x:-x[1]) for i in range(2)]
        if d[0][0][0] != d[1][0][0]:
            ans = -d[0][0][1]-d[1][0][1]
            for i in range(len(d[0])):
                ans += d[0][i][1]
            for i in range(len(d[1])):
                ans += d[1][i][1]
        else:
            ans = -d[0][0][1]-d[1][1][1]
            for i in range(len(d[0])):
                ans += d[0][i][1]
            for i in range(len(d[1])):
                ans += d[1][i][1]
            ans2 = -d[0][1][1]-d[1][0][1]
            for i in range(len(d[0])):
                ans2 += d[0][i][1]
            for i in range(len(d[1])):
                ans2 += d[1][i][1]
            ans = min(ans,ans2)
    print(ans)
#D
def D():
    return

#E
def E():
    s = S()
    if s[-1] == "1":
        print(-1)
        quit()
    s.pop(-1)
    if s != s[::-1]:
        print(-1)
        quit()
    n = len(s)
    ans = [[i+1,i+2] for i in range(n)]
    s = s[:n//2+n%2]
    m = (n+1)//2
    k = 0
    for i in range(len(s)):
        if s[i] == "0":k += 1
    if k == len(s):
        print(-1)
        quit()
    for k in range(len(s)):
        if s[k] == "0":break
    if k == len(s)-1 and s[-1] == "1":
        for i, j in ans:
            print(i,j)
        quit()
    for i in range(k,len(s)):
        if s[i] == "1":
            print(-1)
            quit()
        ans[k-i-1] = [ans[-1][1],m]

    for i, j in ans:
        print(i,j)


#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    E()