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:
#!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
    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()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
s = input()
N = len(s)
if s[-1] == "1" or s[0] == "0" or s[:N-1] != s[:N-1][::-1]:
    print("-1")
else:
    flag = False
    num = 0
    for i in range(N // 2):
        if flag:
            if s[i] == "1":
                num = -1
                break
        else:
            if s[i] == "0":
                flag = True
            else:
                num = i
    if num != -1:
        for i in range(num + 1):
            print("{} {}".format(i+1, i+2))

        if N != 2:
            for i in range(num + 2, N):
                print("{} {}".format(1, i+1))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def answer():
    s = input()
    n = len(s)
    n_wo_last = n - 1
    must_be = (s[0] == '1' and s[-2:] == '10' and
               s[:n_wo_last//2 + 1][::-1] == s[(n_wo_last - n_wo_last//2 - 1):-1])
    if not must_be:
        print('-1')
        return

    tree_elems = []
    vertex_used_num = 1
    center = 1
    one_leftmost = None
    candidates = s[1:((n_wo_last - 1)//2 + 1)] + '0'

    def append_vertex(root):
        nonlocal vertex_used_num
        nonlocal tree_elems
        new_vertex = vertex_used_num + 1
        vertex_used_num += 1
        tree_elems.append((root, new_vertex))
        if len(tree_elems) > n:
            print('-1')
            return
        return new_vertex

    for i, c in enumerate(candidates):
        contiguous_size = i + 2
        if c == '0':
            if one_leftmost is not None:
                one_rightmost = contiguous_size - 1
                now_root = center
                loop_num = one_rightmost - one_leftmost + 1
                for _ in range(loop_num):
                    now_root = append_vertex(now_root)
                loop_num = one_leftmost - 1
                for _ in range(loop_num):
                    append_vertex(now_root)
                one_leftmost = None
        else:
            if one_leftmost is None:
                one_leftmost = contiguous_size
    if vertex_used_num > n:
        print('-1')
        return
    loop_num = n - vertex_used_num
    for _ in range(loop_num):
        append_vertex(center)
    for tree_elem in tree_elems:
        print(tree_elem[0], tree_elem[1])


if __name__ == '__main__':
    answer()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def answer():
    s = input()
    n = len(s)
    n_wo_last = n - 1
    must_be = (s[0] == '1' and s[-2:] == '10' and
               s[:n_wo_last//2 + 1][::-1] == s[(n_wo_last - n_wo_last//2 - 1):-1])
    if not must_be:
        print('-1')
        return

    tree_elems = []
    vertex_used_num = 1
    center = 1
    one_leftmost = None
    candidates = s[1:((n_wo_last - 1)//2 + 1)] + '0'
    for i, c in enumerate(candidates):
        contiguous_size = i + 2
        if c == '0':
            if one_leftmost is not None:
                one_rightmost = contiguous_size - 1
                now_root = center
                loop_num = one_rightmost - one_leftmost + 1
                for _ in range(loop_num):
                    new_vertex = vertex_used_num + 1
                    vertex_used_num += 1
                    tree_elems.append((now_root, new_vertex))
                    now_root = new_vertex
                loop_num = one_leftmost - 1
                for _ in range(loop_num):
                    new_vertex = vertex_used_num + 1
                    vertex_used_num += 1
                    tree_elems.append((now_root, new_vertex))
                one_leftmost = None
        else:
            if one_leftmost is None:
                one_leftmost = contiguous_size
    if vertex_used_num > n:
        print('-1')
        return
    loop_num = n - vertex_used_num
    for _ in range(loop_num):
        new_vertex = vertex_used_num + 1
        vertex_used_num += 1
        tree_elems.append((center, new_vertex))
    for tree_elem in tree_elems:
        print(tree_elem[0], tree_elem[1])


if __name__ == '__main__':
    answer()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


def answer():
    s = input()
    n = len(s)
    n_wo_last = n - 1
    must_be = (s[0] == '1' and s[-2:] == '10' and
               s[:n_wo_last//2 + 1][::-1] == s[(n_wo_last - n_wo_last//2 - 1):-1])
    if not must_be:
        print('-1')
        return

    tree_elems = []
    vertex_used_num = 1
    center = 1
    one_leftmost = None
    for i, c in enumerate(s[1:(n_wo_last//2 + 1 - 1)] + '0'):
        contiguous_size = i + 2
        if c == '0':
            if one_leftmost is not None:
                one_rightmost = contiguous_size - 1
                now_root = center
                for _ in range(one_rightmost - one_leftmost + 1):
                    new_vertex = vertex_used_num + 1
                    vertex_used_num += 1
                    tree_elems.append((now_root, new_vertex))
                    now_root = new_vertex
                for _ in range(one_leftmost - 1):
                    new_vertex = vertex_used_num + 1
                    vertex_used_num += 1
                    tree_elems.append((now_root, new_vertex))
                one_leftmost = None
        else:
            if one_leftmost is None:
                one_leftmost = contiguous_size
    if vertex_used_num > n:
        print('-1')
        return
    for _ in range(n - vertex_used_num):
        new_vertex = vertex_used_num + 1
        vertex_used_num += 1
        tree_elems.append((center, new_vertex))
    for tree_elem in tree_elems:
        print(tree_elem[0], tree_elem[1])


if __name__ == '__main__':
    answer()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

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

S = s_in()
N = len(S)

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
a=list(input())
if a[0]=='0' or a[-1]=='1':
  print(-1)
  exit()
for i in range(len(a)-1):
  if a[i]=='1':
    print(i+1,i+2)
  else:
    print(1,i+2)

Submission status: Wrong Answer

Solution code:
a=list(input())
if a[0]=='0' or a[-1]=='1':
  print(-1)
  exit()
for i in range(len(a)):
  if a[i]=='1':
    print(i,i+1)
  else:
    print(1,i+1)

Submission status: Wrong Answer

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 i == 0: continue
        if c == '1':
            e.append((i-k, i+1))
            if k > 0:
                e.append((i-k+1, i+1))
                for j in range(k-1): e.append((i-k+j+1, i-k+j+2))
            k = 0
        else:
            k += 1
    e.append((n-k, n))
    for u,v in e: print(u,v)
f(input())

Submission status: Wrong Answer

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

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

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:
                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]
                
        
        for i in range(n-1):
            print ("{0} {1}".format(ret[i][0], ret[i][1]))

Submission status: Wrong Answer

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-1)/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 == 0:
            i = int(n/2)-1
            if x[i] == "1":
                ret[i] = [a,b]
            else:
                for j in range(i):
                    if ret[n-j-2][1] == b:
                        ret[n-j-2][1] = a
                ret[i] = [a,i+2]
                
        
        for i in range(n-1):
            print ("{0} {1}".format(ret[i][0], ret[i][1]))

Submission status: Wrong Answer

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]=="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: Wrong Answer

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]=="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: Wrong Answer

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

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

# 1頂点に全部ついた状態から始める
e = [list(range(2, l+1))] + [[] for _ in range(l-1)]
now = 0
h = (l-1) // 2
for i in range(h, 0, -1):
  c = s[i]
  if c == '0':
    continue
  # now の木から子をi個取り出して繋げる
  nowl = len(e[now])
  e[l-i-1] = e[now][-i:]
  e[now] = e[now][:nowl-i]
  now = l-i-1

for i, arr in enumerate(e):
  for a in arr:
    print(i+1, a)

Submission status: Wrong Answer

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 + 1
            temptemp += 1
        else:
            print(temp, temptemp+1) 
            temptemp += 1

main(vs)

Submission status: Wrong Answer

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:
        for i in range(int((n-1)/2)):
            if x[i] == "1":
                # ret[i] = (str(i+1) + " " + str(i+2))
                ret[i] = [i+1,i+2]
                ret[n-i-2] = [n-i-1+1,n-i-2+1]
            else:
                for j in range(i):
                    if ret[j][1] == i+1:
                        ret[j][1] = i+2
                    if ret[n-j-2][1] == n-i-1+1:
                        ret[n-j-2][1] = n-i-2+1
                ret[i] = [i+1,i+2]
                ret[n-i-2] = [n-i-1+1,n-i-2+1]
                
        for i in range(n-1):
            print ("{0} {1}".format(ret[i][0], ret[i][1]))

Submission status: Wrong Answer

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):
        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 + 1
            temptemp += 1
        else:
            print(temp, temptemp+1) 
            temptemp += 1

main(vs)

Submission status: Wrong Answer

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

if 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)]

X = 0
for i in range(N-1):
    T[X].append(i + 1)
    X += (S[i] == "1")

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappop, heappush, heappushpop
def inpl(): return map(int, input().split())

S = input()
N = len(S)
tmp = (N-1)//2

answer = []

if S[-1] == "1":
    print(-1)
elif S[0] == "0":
    print(-1)
elif S[:tmp] != S[-tmp-1:-1][::-1]:
    print(-1)
else:
    M = N-1
    tmp = []
    mode = 0
    x = M//2
    for i in range(x, N):
        if S[i] == "1":
            if mode == 0:
                start = i
                mode = 1
        else:
            if mode == 1:
                tmp.append([i, i-start])
                mode = 0
    if mode == 1:
        tmp.append([x, x-start])
    now = 2
    for a, b in tmp:
        answer.append("1 {}".format(now))
        now += 1
        for i in range(b-1):
            answer.append("{} {}".format(now-1, now))
            now += 1
        tmp = now - 1
        for _ in range(a-b):
            answer.append("{} {}".format(tmp, now))
            now += 1
    if len(answer) > N - 1:
        print(-1)
    else:
        remain = N - len(answer) - 1
        for _ in range(remain):
            answer.append("1 {}".format(now))
            now += 1
        assert len(answer) == N - 1
        print(*answer, sep="\n")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
s = input()
if s[-1] == '1' or s[-2] == '0' or s[0] == '0':
    print(-1)
else:
    k, l = None, None
    for i in range(1, len(s)-2):
        if s[i] == '0':
            k = i
            break
    for i in range(len(s)-2, -1, -1):
        if s[i] == '0':
            l = i
            break
    ok = True
    if k is not None and l is not None and k != l:
        for i in range(k, l+1):
            if s[i] == '1':
                ok = False
                break
    if not ok: print(-1)
    elif k is None and l is None:
        for i in range(len(s)-1):
            print(i+1, i+2)
    elif len(s) - l - 1 != k + 1: print(-1)
    else:
        for i in range(k):
            print(i+1, i+2)
        for i in range(k+1, len(s)):
            print(1, i+1)

Submission status: Wrong Answer

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+1])
    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+1])

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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+1])
    else:
        for i in range((n-1)/2+1):
            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-1):
            res_list.append([rep,i+(n-1)/2+1])

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

Submission status: Wrong Answer

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

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

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
        for i in range(old+1,n+1):
            print(('{} {}'.format(old,i)))

Submission status: Wrong Answer

Solution code:
s = input()
ans = []
a = 1
if s[0] == "0" or s[-1] == "1":
  print(-1)
  exit()
for i in range(len(s)-1):
  if s[i] == "0":
    break
else:
  for i in range(len(s)-1):
    ans.append([a,a+1])
    a+=1
  for i in ans:
    print(*i)
  exit()
ok = set()
for i in range(1,len(s)):
  if s[i] == "1":
    if i+1 in ok:
      continue
    if a+i+1 > len(s):
      print(-1)
      exit()
    for j in range(i+1):
      ans.append([a,a+j+1])
    ok.add(i+1)
    for j in ok.copy():
      ok.add(j+i+1)
    a += i+1
  else:
    if i+1 in ok:
      print(-1)
      exit()
if len(ans) != len(s)-1:
  while len(ans) <= len(s)-1:
    a+=1
    ans.append([1,a])
for i in ans:
  print(*i)

Submission status: Wrong Answer

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

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

if n > 3 and s[2] != '1':
    print("-1")
    exit(0)

itermx = (n-1)//2

ans = "{0} {1}"
nx = 2
for i in range(itermx,-1,-1):
    if s[i] == '1':
        if s[:i] != ("1"*i):
            print("-1")
            exit(0)

        if i != 0:
            print(ans.format(1,2))
        for j in range(2,2+i-1):
            print(ans.format(j,j+1))

        for j in range((2+i),n+1):
            print(ans.format(1,j))

        exit(0)

Submission status: Wrong Answer

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

if S[-1] == "1":
    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: Wrong Answer

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 - 1):
            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):
            res_list.append([rep,i+n/2+1])
    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+1])

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

Submission status: Wrong Answer

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 - 1):
            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):
            res_list.append([rep,i+n/2+1])
    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+1])

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

Submission status: Wrong Answer

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

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

for i in range(N // 2):
    if S[i] != S[N - i - 2]:
        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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

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()