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:
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()
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 (s2[::-1] != s2):
    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:
import re

def main():
    s = input()
    n = len(s)

    if s[-1] == '1':
        print(-1)
        return

    if s == '00':
        print(-1)
        return

    if re.fullmatch('1+0', s):
        for i in range(1, n):
            print(i, i+1)
        return

    if re.fullmatch('10*10', s):
        for i in range(1, n):
            print(1, i+1)
        return

    print(-1)

main()

Submission status: Wrong Answer

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

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

R = []
for i in range(N // 2):
    if S[i] == "1":
        if S[N - i - 2] == "1":
            R.append(i + 1)
        else:
            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()
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()
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(S):
    N = len(S)

    if S[0] == '0' or S[-1] == '1':
        return None

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

    mxsz = 1
    for i in range((N - 2) // 2):
        if S[i] == '0' and S[i + 1] == '1':
            return None
        if S[i + 1] == '1':
            mxsz = i + 2

    G = []
    # print(mxsz)
    for i in range(2, mxsz + 2):
        G.append((i - 1, i))

    for i in range(mxsz + 2, N + 1):
        G.append((1, i))

    return G


def main():
    ans = solve(inp())
    if ans is None:
        print('-1')
        return
    for (p, q) in ans:
        print(p, q)


if __name__ == '__main__':
    main()

Submission status: 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)

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)

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

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

        exit(0)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    s = [int(c) for c in S()]
    if s[0] != 1 or s[-1] == 1:
        return -1
    n = len(s)
    for i in range(1,n):
        if s[i-1] != s[n-i-1]:
            return -1
    r = ['1 2']
    c = 1
    for i in range(3,n+1):
        if s[i-3] == 1 and (s[i-1] == 1 or s[i-2] == 1):
            c = i - 1
        r.append('{} {}'.format(c,i))

    return '\n'.join(r)


print(main())

Submission status: Wrong Answer

Solution code:
S = input()
def is_asynmetric(S):
  for i in range(len(S) // 2):
    if S[i] != S[-(i + 2)]:
      return True
  else:
    return False
if S[0] != '1' or S[-2:] != '10':
  print(-1)
elif is_asynmetric(S):
  print(-1)
else:
  print('1 2')
  edge = 2
  for i, s in enumerate(S[1:-1], 3):
    print(edge, i)
    edge += int(s)

Submission status: Wrong Answer

Solution code:
S = input()
print(-1)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    s = [int(c) for c in S()]
    if s[0] != 1 or s[-1] == 1:
        return -1
    n = len(s)
    for i in range(1,n):
        if s[i-1] != s[n-i-1]:
            return -1
    r = ['1 2']
    c = 1
    for i in range(3,n+1):
        if s[i-2] == 1 and s[i-3] == 1:
            c = i - 1
        r.append('{} {}'.format(c,i))

    return '\n'.join(r)


print(main())

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
flag=False
for i in range(n//2):
    if s[i]!=s[-i-2]:
        flag=True
        break
if flag or s[0]=="0" or s[-1]=="1":
    print(-1)
else:
    print("2 1")
    head=2
    for i in range(3,n//2+2):
        print(str(i)+" "+str(head))
        if s[i-2]=="1":
            head=i
    i+=1
    while i<=n:
        print(str(i)+" "+str(head))
        i+=1

Submission status: Wrong Answer

Solution code:
s = input().strip()
n = len(s)
s = {i + 1 for i in range(n) if s[i] == '1'}

if n in s or 1 not in s or any(n - x not in s for x in range(1, n)):
    print(-1)
else:
    s = sorted(s)
    c = 1
    e = []
    for i in range(1, len(s)):
        while c < s[i]:
            e.append((c, s[i]))
            c += 1
    e.append((c, n))
    e = [str(u) + ' ' + str(v) for u, v in e]
    print(*e, sep='\n')

Submission status: Wrong Answer

Solution code:
s = input().strip()
n = len(s)
s = {i + 1 for i in range(n) if s[i] == '1'}

if n in s or 1 not in s or n - 1 not in s:
    print(-1)
else:
    s = sorted(s)
    c = 1
    e = []
    for i in range(1, len(s)):
        while c < s[i]:
            e.append((c, s[i]))
            c += 1
    e.append((c, n))
    e = [str(u) + ' ' + str(v) for u, v in e]
    print(*e, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import itertools
S = input()
N = len(S)
S = '0' + S
if S[:2] == '01' and S == S[::-1]:
    B = set([i for i, v in enumerate(S[:(N + 1) // 2 + 1]) if v == '1'])
    before = 1
    for i in range(2, N + 1):
        print(before, i)
        if i - 1 in B and i < max(B) + 2:
            before = i
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math

s = input()

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

if not possible:
  print(-1)
elif N == 2:
  if s[1] == "1" and s[2] == "0":
    print(1, 2)
  else:
    print(-1)
elif N == 3:
  if s[1] == "1" and s[2] == "1":
    print(1,2)
    print(2,3)
  else:
    print(-1)
else:
  destination = [1] * (N+1)
  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: Time Limit Exceeded

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

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

path = {1:[v for v in range(2, n+1)]}
u_cur, v_cur = 1, 2
for i in range(n//2-1, 0, -1):
    if s[i] == '1':
        path[v_cur] = []
        for _ in range(i):
            v_tar = path[u_cur].pop()
            path[v_cur].append(v_tar)
        u_cur, v_cur = v_cur, path[v_cur][0]
for u, vs in path.items():
    for v in vs:
        print(*(u, v))

Submission status: Time Limit Exceeded

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

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

# 1頂点に全部ついた状態から始める
e = [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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# E
s = list(input())
N = len(s)
res = True
if s[0] == "0" or s[N-1] == "1":
    res = False
for i in range(N-1):
    if s[i] != s[N-2-i]:
        res = False
if res == False:
    print(-1)
else:
    k = 1
    for i in range(N-1):
        if s[i] == "1":
            while k < i+1:
                print(str(k)+" "+str(i+1))
                k += 1
        while k < N:
            print(str(k)+" "+str(N))

Submission status: Accepted

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

t=s[:-1]
D=[]
for i in range((len(t)+1)//2):
  if t[i]!=t[-1-i]:
    print(-1)
    exit()
m=1
A=[]
for i in range(1,len(s)//2+1):
    A.append((m,i+1))
    if s[i-1]=='1':
        m=i+1
for i in range(len(s)//2+2,len(s)+1):
    A.append((m,i))
for i in A:
    print(*i)

Submission status: Accepted

Solution code:
S = input()
eda = []
flag = False
N = len(S)
if S[-1] == '1':
  flag = True
if S[0] == '0':
  flag = True
if S[-2] == '0':
  flag = True
for k in range((N-1)//2):
  if S[k] != S[-k-2]:
    flag = True
  if S[k] == '1':
    eda.append(k+1)
if N%2 == 0:
  if S[N//2 -1] == '1':
    eda.append(N//2)
if flag:
  print(-1)
  exit()
ans = []
eda.reverse()
before = eda.pop()
while eda:
  after = eda.pop()
  for k in range(before, after):
    ans.append((k, after))
  before = after
ans.append((before, before+1))
for k in range(before+2, N+1):
  ans.append((before+1, k))
while ans:
  item = ans.pop()
  print(item[0], item[1])

Submission status: Accepted

Solution code:
#from collections import deque
#from heapq import heapify, heappop, heappush
#from bisect import insort, bisect_left
#import sys
#sys.setrecursionlimit(10**9)
#from math import gcd
#from decimal import Decimal
#mod = 1000000007
#mod = 998244353
#N = int(input())
#N, K = map(int, input().split())
S = input()
eda = []
flag = False
N = len(S)
if S[-1] == '1':
  flag = True
if S[0] == '0':
  flag = True
if S[-2] == '0':
  flag = True
for k in range((N-1)//2):
  if S[k] != S[-k-2]:
    flag = True
  if S[k] == '1':
    eda.append(k+1)
if N%2 == 0:
  if S[N//2 -1] == '1':
    eda.append(N//2)
if flag:
  print(-1)
  exit()
ans = []
eda.reverse()
before = eda.pop()
while eda:
  after = eda.pop()
  for k in range(before, after):
    ans.append((k, after))
  before = after
ans.append((before, before+1))
for k in range(before+2, N+1):
  ans.append((before+1, k))
while ans:
  item = ans.pop()
  print(item[0], item[1])
#ans = 0
#for k in range(N):
#print(ans)
#print('Yes')
#print('No')

Submission status: Accepted

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

Submission status: Accepted

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

def check():
    if s[0]=="0" or s[-1] =="1":
        return False
    for i in range(n):
        if s[i] != s[n-i-2]:
            return False
    return True

if not check():
    print(-1)
    exit()

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

Submission status: Accepted

Solution code:
def ex():print(-1);exit()

s=input()
N=len(s)
if not (s[0]=='1' and s[-1]=='0'):
    ex()
for i in range(N//2):
    if s[i]!=s[N-i-2]:
        ex()
ans=[]
m=1
for i in range(1,N//2+1):
    ans.append((m,i+1))
    if s[i-1]=='1':
        m=i+1
for i in range(N//2+2,N+1):
    ans.append((m,i))
for t in ans:
    print(*t)

Submission status: Accepted

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

n = len(s)
size = []
for i in range(1,n//2):
    sl = s[i]
    sr = s[n-2-i]
    if(sl != sr):
        print(-1)
        exit()
    if(sl=='1'):
        size.append(i+1)

size.append(n-1)
ans = []
now = 1
for si in size:
    for j in range(now+1,si+2):
        ans.append(' '.join(map(str,[now,j])))
    now = si+1

print('\n'.join(ans))

Submission status: Accepted

Solution code:
s = input()
if s[0] == "0" or s[-1] == "1":
    print(-1)
    exit()
n = len(s)
if n == 2:
    if s == "10":
        print(1, 2)
        exit()
    else:
        print(-1)
        exit()

m = n // 2
tmp = m + 1
ANS = []
for i in reversed(range(1, m + 1)):
    j = n - i
    if s[i - 1] == "1" and s[j - 1] == "1":
        ANS.append((tmp, i))
        tmp = i
    elif s[i - 1] == "0" and s[j - 1] == "0":
        ANS.append((tmp, i))
    else:
        print(-1)
        exit()
for i in range(m + 2, n + 1):
    ANS.append((m + 1, i))

for a, b in ANS:
    print(a, b)

Submission status: Accepted

Solution code:
import sys
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし


S = LI2()
n = len(S)

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

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


k = S.count(1)  # 1の個数
for i in range(k):
    print(i+1,i+2)

a = 1  # 付け足す辺の端点
b = k+2  # 付け足す頂点のindex
for i in range(n-1):
    if S[i] == 1:
        a += 1
    else:
        print(a,b)
        b += 1

Submission status: Accepted

Solution code:
def main():
    s = "0" + input()
    ans = []
    f = True
    for i in range(len(s)//2):
        if s[i] != s[len(s)-1-i]:
            f = False
            break
    if s[1] == "0" or s[-2] == "0":
        f = False
    if f:
        ans = []
        p = len(s)-1
        for i in reversed(range(1, len(s)-1)):
            c = s[i]
            ans.append([i, p])
            if c == "1":
                p = i
        for u, v in ans:
            print(u, v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    S = "*" + input()
    N = len(S) - 1

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

    edge = []
    cur_u = 1
    cur_v = 2

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

        edge.append([cur_u, cur_v])
        if S[i] == "1":
            cur_u = cur_v
        cur_v += 1

    for i in range(cur_v, N + 1):
        edge.append([cur_u, i])

    for i in range(N - 1):
        print(*edge[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=list(map(int,list(input())))
n=len(s)
# print(s)
if s[-1]==1 or s[0]==0:
    print(-1)
    quit()

for i in range(n-1):
    if s[i]!=s[-2-i]:
        print(-1)
        quit()
s[-1]=1
now=n
for i in range(n-1)[::-1]:
    print(i+1,now)
    if s[i]==1:
        now=i+1

Submission status: Accepted

Solution code:
s = input()

if s[0] == '0' or s[-2] == '0' or s[-1] == '1':  # 's' should be like "1xx...x0"
    print(-1)
elif s[:-1] != s[-2::-1]:
    print(-1)
else:
    half = len(s) // 2
    one_indices = [i+1 for i in range(1, half) if s[i] == '1'] # not including 0 or larger than n//2

    parents = [0] * (len(s) + 1)
    parent_index = 1
    for index in one_indices:
        for i in range(parent_index, index):
            parents[i] = index
        parent_index = index

    root = parent_index + 1
    parents[parent_index] = root
    for index in range(root + 1, len(s) + 1):
        parents[index] = root

    for node, parent in enumerate(parents):
        if parent == 0: # This means node is 0 or the root of the tree.
            continue
        print(node, parent)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

s = input()
n = len(s)

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

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

j = 0
for i in range(1,n):
    if s[i] == "1":
        for k in range(j,i):
            print(k+1,i+1)
        j = i

for k in range(j+1,n):
    print(j+1,k+1)

Submission status: Accepted

Solution code:
s=list(input())
n=len(s)
if s[0]=='0' or s[-1]=='1':
  print(-1)
else:
  s.pop()
  sr=s.copy()
  sr.reverse()
  if s!=sr:
    print(-1)
  else:
    ans=[]
    now=1
    cnt=1
    for x in s:
      if x=='1':
        ans.append([now,now+cnt])
        now+=cnt
        cnt=1
      else:
        ans.append([now,now+cnt])
        cnt+=1
    for x in ans:
      print(x[0],x[1])

Submission status: Accepted

Solution code:
s=input()
n=len(s)
f=1
if s[-1]=="1":
  f=0
if s[0]=="0":
  f=0
for i in range(n-1):
  if s[i]!=s[-2-i]:
    f=0
    break
    
s=s[:-1]+"1"
if f:
  k=0
  for i in range(n):
    if s[i]=="1":
      for j in range(k,i):
        print(j+1,i+1)
      k=i
else:
  print(-1)

Submission status: Accepted

Solution code:
s = input()
if s[-1] == "1":
  print(-1)
  exit()
s = s[:-1]
if s != s[::-1] or s[0] == "0":
  print(-1)
  exit()
s += "1"
n = len(s)
now = 1
for i, t in enumerate(s, 1):
  if t == "1":
    for j in range(now, i):
      print(j, i)
      now = i

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def ng():
    if s[0]=="0" or s[-1]=="1":return True
    for i in range(n):
        if i>n-2-i:break
        if s[i]!=s[n-2-i]:return True
    return False

s=SI()
n=len(s)

if ng():
    print(-1)
    exit()

aa=[]
for i in range(n//2):
    if s[i]=="1":aa.append(i+1)
aa.append(n)

ans=[]
for i in range(len(aa)-1):ans.append([i+1,i+2])

j=len(aa)+1
for i,(a0,a1) in enumerate(zip(aa,aa[1:])):
    for _ in range(a1-a0-1):
        ans.append([i+2,j])
        j+=1

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

Submission status: Accepted

Solution code:
s = input().strip()
n = len(s)
s = "0"+s
flag = 0
if s[n]=="1" or s[1]=="0":
    flag = 1
else:
    for i in range(1,n):
        if s[i]!=s[n-i]:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    A = [1]
    for i in range(2,n):
        if s[i]=="1":
            while A:
                print(A.pop(),i)
            A = [i]
        else:
            A.append(i)
    print(n-1,n)

Submission status: Accepted

Solution code:
import sys
s=input()
n=len(s)
if s[-1]=='1':
  print(-1)
  sys.exit()
if s[0]=='0':
  print(-1)
  sys.exit()
for i in range(n-1):
  if s[i]!=s[n-2-i]:
    print(-1)
    sys.exit()
ans=['1','2']
print(' '.join(ans))
current=2
for i in range(1,n-1):
  ans=[]
  ans.append(str(current))
  ans.append(str(i+2))
  print(' '.join(ans))
  if s[i]=='1':
    current=i+2

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    s=input()
    N=len(s)
    f=1
    if s[-1]=="1" or s[0]=="0":
        f=0
    for i in range(1,N//2+1):
        if s[i-1]!=s[N-i-1]:
            f=0
            break
    if not f:
        print(-1)
        return
    
    il=[]
    edge=[]
    for i in range(1,N//2+1):
        if s[i-1]=="0":
            il.append(i)
        else:
            for j in il:
                edge.append((i,j))
            il=[i]
    i=N//2+1
    for j in il:
        edge.append((i,j))
    j=i
    for i in range(N//2+2,N+1):
        edge.append((j,i))

    for e in edge:
        print(*e)







if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

s = input()[:-1]

if s[0] == "1" and s[-1] == "0":
	k = (len(s)-2)//2

	for i in range(k):
		if s[i] != s[-(2 + i)]:
			print(-1)
			exit()
	else:
		
		la = len(s)

		for i in range(la-2,-1,-1):
			if s[i] == "1":
				print(i+1,la)
				la = i+1
			else:
				print(i+1,la)
else:
	print(-1)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
ok = s[0] == '1' and s[n-1] == '0'
for i in range(n-1):
    ok = ok and s[i] == s[n-2-i]
if not ok:
    print(-1)
    exit()
s2 = s[:n//2]
i = s2.rindex('1')
for k in range(i, n-1):
    print(n, k+1)
while i > 0:
    j = i - 1
    while s[j] != '1':
        j -= 1
    for k in range(j, i):
        print(i+1, k+1)
    i = j

Submission status: Accepted

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

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

else:
    for i in range(N - 1):
        if S[i] != S[N - 2 - i]:
            print(-1)
            break
    else:
        tmp = 1
        for i in range(N - 1):
            if S[i] == '1':
                print(tmp, i + 2)
                tmp = i + 2
            else:
                print(tmp, i + 2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    S = input()
    N = len(S)
    if S[0] == '0' or S[-1] == '1':
        print(-1)
        return
    cnt = 0
    flag = True
    for i in range(N - 1):
        if S[i] != S[N - i - 2]:
            flag = False
            break
        if S[i] == '1':
            cnt += 1
    if not flag:
        print(-1)
        return
    
    edge = []
    for i in range(cnt):
        edge.append((i + 1,i + 2))
    
    extend = 0
    now = cnt + 2
    vertex = 2
    for i in range(1,N - 1):
        if S[i] == '0':
            extend += 1
        else:
            for _ in range(extend):
                edge.append((vertex,now))
                now += 1
            extend = 0
            vertex += 1

    if now == N + 1:
        print('\n'.join(' '.join(map(str,a)) for a in edge))
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
if s[-1] == "1":
    print(-1)
    exit()
if s[:-1] != s[:-1][::-1]:
    print(-1)
    exit()
if s[0] == "0":
    print(-1)
    exit()

before = -1
for i in range(n // 2):
    if s[i] == "1":
        num = i - before
        for j in range(num):
            print(before+2, i+2-j)
        before = i

for j in range(n-2-before):
    print(before+2, before+3+j)