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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

s = input()
N = len(s)
if s[0] == '0' or s[-1] == '1' or s[:-1] != s[:-1][::-1]:
    print(-1)
    exit()
subtree = [[] for _ in range(N+1)]
prev = 1
for i in range(2, N+1):
    if s[i-1] == '1' or i == N:
        subtree[i] = [prev] + [1] * (i-prev-1)
        prev = i

i = 1
def dfs(size):
    global i
    v = i
    for c in subtree[size]:
        i += 1
        print(v, i)
        dfs(c)

dfs(N)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    s = input()
    l = len(s)
    if s[0] != "1" or s[-1] != "0":
        print(-1)
    else:
        b = True
        c = 1
        for i in range(l//2):
            if b:
                if s[i] == "0":
                    b = False
                else:
                    if s[l-i-2] == "1":
                        c = i+1
                    else:
                        print(-1)
                        exit()
            else:
                if s[i] == "1":
                    print(-1)
                    exit()
        ans = []
        for i in range(c):
            ans.append((i+1,i+2))
        for i in range(l-c-1):
            ans.append((1,l-i))
        for x,y in ans:
            print(x,y)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
if s[0]=="0" or s[-1]=="1" or any(s[i]!=s[n-i-2] for i in range(n-1)):
	print(-1)
	exit()
ans=[]
now=0
for i,c in enumerate(s[:-1]):
	if c=="1":
		ans.append("{} {}".format(now,i+1))
		now=i+1
	else:
		ans.append("{} {}".format(now,i+1))
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
s = input()
N = len(s)
for i in range(N//2-1,-1,-1):
  if s[i]=='1':
    if s[N-2-i]!='1':
      print(-1)
      break
else:
  if s[0]=='0' or s[-1]=='1':
    print(-1)
  else:
    s = list(s)
    s[-1] = '1'
    ls = []
    for i in range(N):
      if s[i]=='1':
        ls.append(i)
    ps = 0
    for i in range(N-1):
      if i==ls[ps]:
        ps += 1
      print(i+1,ls[ps]+1)

Submission status: Wrong Answer

Solution code:
s = input()
N = len(s)
flag = False
j = -1
for i in range(N//2-1,-1,-1):
  if s[i]=='1':
    if s[N-2-i]!='1':
      print(-1)
      break
    flag = True
  elif flag:
    print(-1)
    break
else:
  if s[0]=='0' or s[-1]=='1':
    print(-1)
  else:
    for i in range(N//2):
      if s[i]=='1':
        j = i
    m = j+1
    for i in range(1,1+m):
      print(i,i+1)
    for i in range(1+m+1,N+1):
      print(1,i)

Submission status: Wrong Answer

Solution code:
S=[int(c) for c in input()]
N=len(S)
r=all([S[i]==S[N-i-2] for i in range(N//2)]) and S[0] and not S[-1]
t=[(1,2)]
e=2
for i in range(1,(N-1)//2):
    t.append((e,i+2))
    if S[i]:
        e=i+2
f=1
if N%2==0:
    t.append((e,N-e+1))
    if S[N//2-1]:
        f=0
for i in range(0,(N-1)//2):
    t.append(((e if t[i][0]==e and f else N-t[i][0]+1),(e if t[i][1]==e and f else N-t[i][1]+1)))
if r:
    print(*[str(l[0])+" "+str(l[1]) for l in t],sep='\n')
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
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' or S[N] == '1':
        return None
    prev = 1
    graph = []
    for i in range(1, N//2 + 1):
        if S[i] != S[N-i]:
            return None
        if S[i] == '0':
            continue
        for x in range(prev, i):
            graph.append('{} {}'.format(x, i))
    for x in range(prev, N):
        graph.append('{} {}'.format(x, N))
    return graph

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

# 42

Submission status: Wrong Answer

Solution code:
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):
            print(i, n)
        prev = n
    for i in range(prev,N):
        print(i, N)
      
    return graph

solve(S)

Submission status: Wrong Answer

Solution code:
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':
    print(-1); exit()
S = ['-'] + S

def solve(S):
    prev = 1
    graph = []
    for i in range(1, N//2 + 1):
        if S[i] != S[N-i]:
            print(-1); exit()
        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)

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':
        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):
            print(i, n)
        prev = n
    for i in range(prev,N):
        print(i, N)

solve(S)

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':
        print(-1)
        return
    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 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' or S[N] == '1':
        print(-1)
        return
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            print(-1)
            return
        if S[n] == '0':
            continue
        for i in range(prev,n):
            print(i, n)
        prev = n
    for i in range(prev,N):
        print(i, N)
      
    return graph

solve(S)

Submission status: Wrong Answer

Solution code:
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' or 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):
            print(i, n)
        prev = n
    for i in range(prev,N):
        print(i, N)
      
    return graph

solve(S)

Submission status: Wrong Answer

Solution code:
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
    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):
            print(i, n)
        prev = n
    for x in range(prev, N):
        print(x, N)

solve(S)

Submission status: Wrong Answer

Solution code:
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
    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):
            print(i, n)
        prev = n
    for x in range(prev, N):
        print(x, N)

solve(S)

Submission status: Wrong Answer

Solution code:
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':
    print(-1); exit()
S = ['-'] + S
def solve(S):
    prev = 1
    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):
            print(i, n)
        prev = n
    for x in range(prev, N):
        print(x, N)

solve(S)

Submission status: Wrong Answer

Solution code:
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':
    print(-1); exit()
S = ['-'] + S
def solve(S):
    prev = 1
    for i in range(1, N//2 + 1):
        if S[i] != S[N-i]:
            print(-1); exit()
        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)

solve(S)

Submission status: Wrong Answer

Solution code:
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':
    print(-1); exit()
S = ['-'] + S

def solve(S):
    prev = 1
    graph = []
    for i in range(1, N//2 + 1):
        if S[i] != S[N-i]:
            print(-1); exit()
        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)

solve(S)

Submission status: Wrong Answer

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)
    p=pmax
    if num==2:
        lst.append([pmax,pmax+1])
        usedlst.add(pmax+1)
        p=pmax+1
        pmax=p+1
    else:
        for i in range(1,num-oddscount-2):
            lst.append([pmax,pmax+i])
            usedlst.add(pmax+i)
        pmax+=num-oddscount-2
        oddscount+=num
evenP=p
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: Wrong Answer

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)
    p=pmax
    if num==2:
        lst.append([pmax,pmax+1])
        usedlst.add(pmax+1)
        p=pmax+1
    else:
        for i in range(1,num-oddscount-1):
            lst.append([pmax,pmax+i])
            usedlst.add(pmax+i)
        pmax+=num-oddscount-2
        oddscount+=num
evenP=p
print(lst)
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: Wrong Answer

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
p+=2
pmax=p+1
for num in even:
    lst.append([p,pmax])
    usedlst.add(p)
    usedlst.add(pmax)
    p=pmax
    if num==2:
        lst.append([pmax,pmax+1])
        usedlst.add(pmax+1)
        p=pmax+1
    else:
        for i in range(1,num-oddscount-1):
            lst.append([pmax,pmax+i])
            usedlst.add(pmax+i)
        pmax+=num-oddscount-2
        oddscount+=num
evenP=p

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

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
p+=1
pmax=p+1
for num in even:
    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
evenP=p

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

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(1,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
oddsP=p

oddscount=0
p+=1
pmax=p+1
for num in even:
    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
evenP=p

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

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()
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(1,length+1+(len(S)%2==0)):
    if S[i-1]=="1":
        if i%2==1:
            odds.append(i)
        else:
            even.append(i)

for i in range(2*(10**5)):
    lst.append([1,1])

Submission status: Wrong Answer

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()
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(1,length+1+(len(S)%2==0)):
    if S[i-1]=="1":
        if i%2==1:
            odds.append(i)
        else:
            even.append(i)

Submission status: Wrong Answer

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()
length=(len(S)-1)//2
for i in range(length):
    if S[i]!=S[-2-i]:
        print(-1,"imlp")
        exit()

odds=[]
even=[]
lst=[]
for i in range(1,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
for num in odds:
    lst.append([p,pmax])
    p=pmax
    for i in range(1,num-oddscount-1 + (num==1) * 2):
        lst.append([pmax,pmax+i])
    pmax+=num-oddscount-2
oddsP=p
pmax=p+1
oddscount=0

for num in even:
    lst.append([p,pmax])
    p=pmax
    for i in range(1,num-oddscount-1):
        lst.append([pmax,pmax+i])
    pmax+=num-oddscount-2
evenP=p
if odds and even:
    D=[oddsP]+list(range(evenP,len(S)+1))+[evenP]
elif odds:
    print(lst)
    print(oddsP)
    D=[oddsP]+list(range(oddsP+1,len(S)+1))
else:
    D=[evenP]+list(range(evenP+1,len(S)+1))
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: Wrong Answer

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()
length=(len(S)-1)//2
for i in range(length):
    if S[i]!=S[-2-i]:
        print(-1,"imlp")
        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
for num in odds:
    lst.append([p,pmax])
    p=pmax
    for i in range(1,num-oddscount-1):
        lst.append([pmax,pmax+i])
    pmax+=num-oddscount-2
oddsP=p
pmax=p+1
oddscount=0

for num in even:
    lst.append([p,pmax])
    p=pmax
    for i in range(1,num-oddscount-1):
        lst.append([pmax,pmax+i])
    pmax+=num-oddscount-2
evenP=p
if odds and even:
    D=[oddsP]+list(range(evenP,len(S)+1))+[evenP]
elif odds:
    D=[oddsP]+list(range(oddsP,len(S)+1))
else:
    D=[evenP]+list(range(evenP+1,len(S)+1))
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: Wrong Answer

Solution code:
s=input()
n=len(s)
if s[-1]=="1" or s[:(n-1)//2] != s[n-2:n//2-1:-1]:
  print(-1)
  exit()
x=s[1:n//2]
cnt = 2
ans = []
for i in range(len(x)):
  if x[i] == "1":
    k = i+2
    ans.append((1,cnt))
    for j in range(1,k):
      ans.append((cnt,cnt+j))
    cnt += k
for i in range(cnt,n+1):
  ans.append((1,i))
for edge in ans:
  print(*edge)

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
if s[-1]=="1" or s[:(n-1)//2] != s[n-2:n//2-1:-1]:
  print(-1)
  exit()
x=s[:n//2]

Submission status: Wrong Answer

Solution code:
def examC():
    N = I()
    A = LI()
    d0 = defaultdict(int); d0[0] = 0
    d1 = defaultdict(int); d1[0] = 0
    for i in range(N):
        if i%2==0:
            d0[A[i]] +=1
        else:
            d1[A[i]] +=1
    n0 = sorted(d0.items(),key=lambda x:x[1])
    n1 = sorted(d1.items(),key=lambda x:x[1])
#    print(n0); print(n1)
    if n0[-1][0]!=n1[-1][0]:
        ans = N - n0[-1][1] - n1[-1][1]
    else:
        ans = N - max(n0[-1][1]+n1[-2][1],n0[-2][1]+n1[-1][1])
    print(ans)
    return

def examE():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    flag = -1
    for i in range((N+1)//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if flag>=0 and S[i]=="1":
            print(-1)
            return
        if S[i]=="0" and flag<0:
            flag = i
    if flag<0:
        flag = (N+1)//2
#    print(flag)
    ans = [[] for _ in range(N-1)]
    for i in range(N-1):
        if i<flag:
            ans[i] = [i+1,i+2]
        else:
            ans[i] = [flag+1, i + 2]
    for v in ans:
        print(" ".join(map(str,v)))
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

Submission status: Wrong Answer

Solution code:
def examC():
    N = I()
    A = LI()
    d0 = defaultdict(int); d0[0] = 0
    d1 = defaultdict(int); d1[0] = 0
    for i in range(N):
        if i%2==0:
            d0[A[i]] +=1
        else:
            d1[A[i]] +=1
    n0 = sorted(d0.items(),key=lambda x:x[1])
    n1 = sorted(d1.items(),key=lambda x:x[1])
#    print(n0); print(n1)
    if n0[-1][0]!=n1[-1][0]:
        ans = N - n0[-1][1] - n1[-1][1]
    else:
        ans = N - max(n0[-1][1]+n1[-2][1],n0[-2][1]+n1[-1][1])
    print(ans)
    return

def examE():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    flag = -1
    for i in range((N+1)//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if flag>0 and S[i]=="1":
            print(-1)
            return
        if S[i]=="0" and flag<0:
            flag = i
    if flag<0:
        flag = (N+1)//2+1
#    print(flag)
    ans = [[] for _ in range(N-1)]
    for i in range(N-1):
        if i<=flag:
            ans[i] = [i+1,i+2]
        else:
            ans[i] = [flag+1, i + 2]
    for v in ans:
        print(" ".join(map(str,v)))
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

Submission status: Wrong Answer

Solution code:
def examC():
    N = I()
    A = LI()
    d0 = defaultdict(int); d0[0] = 0
    d1 = defaultdict(int); d1[0] = 0
    for i in range(N):
        if i%2==0:
            d0[A[i]] +=1
        else:
            d1[A[i]] +=1
    n0 = sorted(d0.items(),key=lambda x:x[1])
    n1 = sorted(d1.items(),key=lambda x:x[1])
#    print(n0); print(n1)
    if n0[-1][0]!=n1[-1][0]:
        ans = N - n0[-1][1] - n1[-1][1]
    else:
        ans = N - max(n0[-1][1]+n1[-2][1],n0[-2][1]+n1[-1][1])
    print(ans)
    return

def examE():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    flag = -1
    for i in range((N+1)//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if flag>0 and S[i]=="1":
            print(-1)
            return
        if S[i]=="0" and flag<0:
            flag = i
    if flag<0:
        flag = (N+1)//2
#    print(flag)
    ans = [[] for _ in range(N-1)]
    for i in range(N-1):
        if i<=flag:
            ans[i] = [i+1,i+2]
        else:
            ans[i] = [flag+1, i + 2]
    for v in ans:
        print(" ".join(map(str,v)))
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

Submission status: Wrong Answer

Solution code:
def examC():
    N = I()
    A = LI()
    d0 = defaultdict(int); d0[0] = 0
    d1 = defaultdict(int); d1[0] = 0
    for i in range(N):
        if i%2==0:
            d0[A[i]] +=1
        else:
            d1[A[i]] +=1
    n0 = sorted(d0.items(),key=lambda x:x[1])
    n1 = sorted(d1.items(),key=lambda x:x[1])
#    print(n0); print(n1)
    if n0[-1][0]!=n1[-1][0]:
        ans = N - n0[-1][1] - n1[-1][1]
    else:
        ans = N - max(n0[-1][1]+n1[-2][1],n0[-2][1]+n1[-1][1])
    print(ans)
    return

def examE():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    flag = -1
    for i in range((N+1)//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if flag>0 and S[i]=="1":
            print(-1)
            return
        if S[i]=="0":
            flag = i
    if flag<0:
        flag = (N+1)//2
#    print(flag)
    ans = [[] for _ in range(N-1)]
    for i in range(N-1):
        if i<=flag:
            ans[i] = [i+1,i+2]
        else:
            ans[i] = [flag+1, i + 2]
    for v in ans:
        print(" ".join(map(str,v)))
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examE()