Problem:


Score : 700 points

Problem Statement

You are given a string s of length n.
Does a tree with n vertices that satisfies the following conditions exist?

The vertices are numbered 1,2,..., n.

The edges are numbered 1,2,..., n-1, and Edge i connects Vertex u_i and v_i.

If the i-th character in s is 1, we can have a connected component of size i by removing one edge from the tree.

If the i-th character in s is 0, we cannot have a connected component of size i by removing any one edge from the tree.

If such a tree exists, construct one such tree.

Constraints

2 \leq n \leq 10^5

s is a string of length n consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

s

Output

If a tree with n vertices that satisfies the conditions does not exist, print -1.

If a tree with n vertices that satisfies the conditions exist, print n-1 lines.
The i-th line should contain u_i and v_i with a space in between.
If there are multiple trees that satisfy the conditions, any such tree will be accepted.

Sample Input 1

1111

Sample Output 1

-1

It is impossible to have a connected component of size n after removing one edge from a tree with n vertices.

Sample Input 2

1110

Sample Output 2

1 2
2 3
3 4

If Edge 1 or Edge 3 is removed, we will have a connected component of size 1 and another of size 3. If Edge 2 is removed, we will have two connected components, each of size 2.

Sample Input 3

1010

Sample Output 3

1 2
1 3
1 4

Removing any edge will result in a connected component of size 1 and another of size 3.



Sample input:
1111


Sample output:
-1

Submission status: Accepted

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

def main():
    s = input().strip()
    if s[-1] == '1' or s[0] == '0':
        print(-1)
    else:
        edges = deque([])
        for i in range(len(s)-1):
            if s[i] != s[len(s)-i-2]:
                print(-1)
                return
            elif s[i] == '1':
                edges.append(i)
        edges.append(len(s)-1)
        for i in range(len(s)-1):
            if edges[0] == i:
                edges.popleft()
            print(i+1, edges[0]+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
A=list(input())
N=len(A)

if A[-1]=="1":
    print(-1)
elif A[0]!="1" or A[-2]!="1":
    print(-1)
else:
    for i in range(N-1):
        if A[i]!=A[N-2-i]:
            print(-1)
            exit()
    X=1
    Y=0
    #print(A)
    for i in range(N-1):
        if A[i]=="1":
            print(Y+1,X+1)
            Y=X
            X+=1
        else:
            print(X+1,Y+1)
            X+=1

Submission status: Accepted

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

for i in range((len(s) - 1) // 2):
    # print(i,len(s)- i - 2)
    if s[i] != s[len(s) - i -2]:
        print(-1)
        exit()

sd = s[:-1] + '1'
plist = [i for i, v in enumerate(sd) if v == '1']
# print(plist)
for i,v in enumerate(s[:-1]):
    r = bisect.bisect(plist,i)
    print(i+1,plist[r] + 1)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
s=input()
slen=len(s)-1
slen2=(len(s)-1)//2
iswitch=0
for i in range(slen2):
    if s[i]!=s[slen-i-1]:
        iswitch=1

if s[-1]=='1' or s[0]=='0':
    iswitch=1

if iswitch==1:
    print(-1)
else:
    if slen==1:
        print("1 1")
    elif slen==2:
        print("1 2")
        print("1 3")
    else:
        if True:
            henlist=[]
            mae=1
            jswitch=0
            for i in range(slen):
                now=i+2
                if jswitch==0:
                    if s[now-1]=='1':
                        for i in range(now-mae):
                            henlist.append([mae+i, now])
                        mae=now
                        if now>(len(s))//2:
                            jswitch=1
                    else:
                        pass
                else:
                    henlist.append([mae, now])
        for hl in henlist:
            print(hl[0], hl[1])

Submission status: Accepted

Solution code:
from collections import deque
s = list(input())
n = len(s)

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

s[n-1] = '1'

one =deque([])

for i in range(n):
    if s[i] == '1':
        one.append(i)

for i in range(n-1):
    if s[i] == '0':
        print(i+1,one[0]+1)
    else:
        a = one.popleft()
        print(a+1,one[0]+1)

Submission status: Accepted

Solution code:
def main():
    S = input()
    N = len(S)
    ok = True
    if S[0] == "0" or S[N-1] == "1":
        ok = False
    for i in range(N-1):
        if S[i] != S[N-2-i]:
            ok = False
    if not ok:
        print(-1)
        return
    prev = 1
    for i in range(2, N+1):
        print(prev, i)
        if S[i-2] == "1":
            prev = i


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()

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

print(1,2)
top = 2

for i in range(1,len(s)-1):
    print(top, i + 2)
    if s[i]=='1':
        top = i+2

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


s = S()


if s[0] == '0' or s[-1] == '1' or s[:-1] != s[:-1][::-1]:
    print(-1)
else:
    n = len(s)
    s = s[:-1]
    now_point = 1
    for nxt_point in range(len(s)):
        print(now_point, nxt_point+2)
        if s[nxt_point] == '1':
            now_point = nxt_point+2

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = sys.stdin.readline().rstrip()


def solve(S: str):
    if S[-1] == '1':
        return None
    S = S[:-1]
    if S[::-1] != S:
        return None
    if S[0] == '0':
        return None
    ret = [(1, 2)]
    v = 2
    for i in range(1, (len(S) + 1) // 2):
        ret.append((v, i + 2))
        if S[i] == '1':
            v = i + 2
    for i in range((len(S) + 1) // 2, len(S)):
        ret.append((v, i + 2))

    return ret


ans = solve(S)
if ans:
    for r in ans:
        print(*r)
else:
    print(-1)

Submission status: Accepted

Solution code:

s = input()
len_s = len(s)

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

num = 1
for i in range(len_s - 1):
	if s[i] == '1':
		print('{0} {1}'.format(num, i + 2))
		num = i + 2
	else:
		print('{0} {1}'.format(num, i + 2))

Submission status: Accepted

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

# 1 and n-1 must be exist
if s[0] == "0" or s[-1] == "1":
    print(-1)
    exit()
# x and n-x must be exist at the same
for fs, bs in zip(s[:-1], s[:-1][::-1]):
    if fs != bs:
        print(-1)
        exit()

made = set()
node_num = 0
base = 0
for i, ch in enumerate(s[:-1]):
    if ch == "1" and i+1 not in made:
        node_num += 1
        print(node_num + 1, base + 1)
        base = node_num
        made.add(i+1)
        made.add(n-i-1)
    else:
        node_num += 1
        print(base + 1, node_num + 1)

Submission status: Accepted

Solution code:
s = input()

cnt = 0
# サイズnの連結成分は必ず作れない
# サイズ1の連結成分は必ず作れる
if s[-1] == "1" or s[0] == "0":
    print(-1)
    exit()
    
li = []
for i in range(1, len(s) // 2):
    if s[i] != s[-i-2]:
        print(-1)
        exit()
    if s[i] == "1":
        li.append(i + 1)
        
tree = []
j = 1
for _ in range(len(li)):
    tree.append((j, j + 1))
    j += 1
li.append(len(s))

cnt = 0
for i in range(len(li)):
    cnt += 1
    while cnt < li[i]:
        tree.append((i + 1, j + 1))
        j += 1
        cnt += 1

for edge in tree:
    print(*edge)

Submission status: Accepted

Solution code:
S = input()

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

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

print("1 2")
current_root = 1
for i in range(1, len(S)-1):
    print("{:d} {:d}".format(i+2, current_root+1))
    if i << len(S)//2 and S[i] == "1":
        current_root = i+1

Submission status: Accepted

Solution code:
s = input()

S = '0' + s
N = len(s)


# 葉から順に構築
def f():
    res = []
    r = 1
    C = []
    for i in range(2, N + 1):
        if S[i] == '0':
            C.append(i)
        else:
            res.append((r, i))
            r = i
            for c in C:
                res.append((r, c))
            C = []
    for c in C:
        res.append((r, c))
    return res


ans = (
    '-1' if S[1] == '0' or S[N] == '1' or any(
        S[i] != S[N - i]
        for i in range(1, N)
    ) else
    '\n'.join(
        '{} {}'.format(u, v)
        for u, v in f()
    )
)

print(ans)

Submission status: Accepted

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

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        return None
    if S[N] == '1':
        return None
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    graph += ['{} {}'.format(i,N) for i in range(prev,N)]
    return graph

graph = solve(S)

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

Submission status: Accepted

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

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        return None
    if S[N] == '1':
        return None
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append('{} {}'.format(i,n))
        prev = n
    for i in range(prev,N):
        graph.append('{} {}'.format(i,N))
    return graph

graph = solve(S)

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

Submission status: Accepted

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

S = '-' + input().rstrip()
N = len(S) - 1

def solve(S):
    if S[1] == '0':
        return None
    if S[N] == '1':
        return None
    prev = 1
    graph = []
    for n in range(1,N//2 + 1):
        if S[n] != S[N-n]:
            return None
        if S[n] == '0':
            continue
        for i in range(prev,n):
            graph.append((i,n))
        prev = n
    for i in range(prev,N):
        graph.append((i,N))
    return graph

graph = solve(S)

if graph is None:
    print(-1)
else:
    for x,y in graph:
        print(x,y)

Submission status: Accepted

Solution code:
from sys import exit
def muri():
    print(-1)
    exit()

L = list(map(int, input()))
N = len(L)
if L.pop():
    muri()
if not L[0]:
    muri()
if L != L[::-1]:
    muri()
if N == 2:
    print(1, 2)
    exit()

Ans = []
M = [i for i, l in enumerate(L, 1) if l] 
K = [0] + [m2 - m1 - 1 for m1, m2 in zip(M, M[1:])] + [0]
p = 1
for _ in range(len(M)):
    Ans.append((p, p+1))
    p += 1
p += 1
for j, k in enumerate(K, 1):
    for _ in range(k):
        Ans.append((j, p))
        p += 1

for a in Ans:
    print(*a)

Submission status: Accepted

Solution code:
s = input()
N = len(s)
if s[0]=="0" or s[-1]=="1":
    print(-1)
    exit()
Ans = []
q = [0]
for i in range(1, N//2):
    c, cr = s[i], s[-2-i]
    if c!=cr:
        print(-1)
        exit()
    else:
        if c=="1":
            for u in q:
                Ans.append([u, i])
            q = [i]
        else:
            q.append(i)
i = N//2
if N%2==1:
    for u in q:
        Ans.append([u, i])
    for ans in Ans:
        print(ans[0]+1, ans[1]+1)
        print(N-ans[0], N-ans[1])
else:
    if len(q)==1:
        print(i, i+1)
        for ans in Ans:
            print(ans[0] + 1, ans[1] + 1)
            print(N - ans[0], N - ans[1])
    else:
        v = q.pop()
        for u in q:
            print(v+1, u+1)
            print(v+1, N-u)
        print(i, i+1)
        for ans in Ans:
            print(ans[0] + 1, ans[1] + 1)
            print(N - ans[0], N - ans[1])

Submission status: Accepted

Solution code:
s = input()

n = len(s)

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

#rebuild tree

#record all size
ss = []

for i in range(n-1,-1,-1):
    if s[i] == '1':
        ss.append(i+1)


now_no = 1
now_siz = n
for siz in ss:
    others = now_siz - siz - 1
    for i in range(1,others+1):
        print(now_no,now_no+i)
    print(now_no,now_no+others+1)
    now_no += others+1
    now_siz = siz

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def check_str(s):
    n = len(s) - 1
    if (s[1] != 1) or (s[-1] != 0):
        return False
    else:
        for i in range(1, n / 2):
            if s[i] != s[n - i]:
                return False
    return True

def solve():
    s = [int(_) for _ in raw_input()]
    s.insert(0,0)
    if not check_str(s):
        print '-1'
        return
    sub = []
    for i in range(len(s)):
        if s[i] == 1:
            sub.append(i)
    ## Create tree caterpillar type
    ## body
    body_leng = len(sub) + 1
    for i in range(1, body_leng):
        print str(i) + ' ' + str(i+1)
    ## legs
    cnt = body_leng
    for i in range(1, body_leng - 1):
        num_legs = sub[i] - sub[i-1] - 1
        for j in range(cnt + 1, cnt + num_legs + 1):
            print str(i+1) + ' ' + str(j)
        cnt += num_legs

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

ans = []
u_cur, v_cur = 1, 2
n_prev = 0
for i in range(1, n//2):
    if s[i] == '1':
        for _ in range(i-n_prev):
            ans.append((u_cur, v_cur))
            v_cur += 1
        ans.append((v_cur, u_cur))
        u_cur, v_cur = v_cur, v_cur+1
        n_prev = i+1
for v in range(v_cur, n+1):
    ans.append((v_cur-1, v))
for a in ans:
    print(*a)

Submission status: Accepted

Solution code:
s = list(input())

n = len(s)

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

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

s[n-1] = '1'

i = 0
while i < n-1:
    p = -1
    for j in range(i+1, n):
        if s[j] == '1':
            p = j
            break
    for k in range(i, p):
        print(k+1, p+1)
    i = p

Submission status: Accepted

Solution code:
inp=[int(x) for x in list(input())]
length=len(inp)
x,y=(0,length-2)

if (not inp[0]==inp[length-2]==1) or inp[length-1]==1:
  print(-1)
  exit()

while x<y:
  if inp[x]!=inp[y]:
    print(-1)
    exit()
  else:
    x+=1
    y-=1

now=1
num=1
if length<=4:
  for x in inp:
    num+=1
    if x:
      print (now,num)
      now=num
    else:
      print (now,num)
    if num==length:
      break
else:
  for x in inp:
    num+=1
    if x:
      print (now,num)
      if num!=length-1:
        now=num
    else:
      print (now,num)
    if num==length:
      break

Submission status: Accepted

Solution code:
s = input()

flag = False
if s[0] == "0": flag = True
if s[-1] == "1": flag = True

N = len(s) // 2 + len(s) % 2
for i in range(N):
  if s[i] != s[-2 - i]:
    flag = True

if flag:
  print("-1")
  exit()

re = 1
for i in range(1, len(s)):
  print(re, i + 1)
  if s[i - 1] == "1":
    re = i + 1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def solve(s):
    n = len(s)

    if s[0] != '1':
        print(-1)
        return
    if s[-1] != '0':
        print(-1)
        return
    for i in range((n - 1) // 2):
        if s[i] != s[n - 2 - i]:
            print(-1)
            return
    edges = [(1, 2)]
    s = s[: n // 2]
    p = 1
    if 3 < n and s[1] == '1':
        p = 2
    for i in range(1, n // 2):
        edges.append((p, i + 2))
        if s[i] == '1':
            p = i + 2
    for i in range(n // 2 + 1, n):
        edges.append((p, i + 1))

    for uv in edges:
        u, v = uv
        print('{} {}'.format(u, v))


def main():
    s = input()

    solve(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 必要条件まではわかったけど、必ず任意の木を構築できる
# という考えには至らず。
# https://betrue12.hateblo.jp/entry/2018/09/30/125042
# の図とC++コードを参考にする
#
# まず1文字目は必ず1。最初は以下のようなエッジを構築。
#                 2(top)
#                /
#               1
# "top"は、つぎの頂点がつながる先を表す。
#
# 2文字目が0の場合:  topは移動しない
#                 2(top)
#                / \
#               1   3
# 2文字目が1の場合:  topは移動する
#                   3(top)
#                  /
#                 2
#                /
#               1


import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(S):
    # 必要条件の確認
    if S[-1] == '1':
        return -1
    if S[0] == '0':
        return -1
    size = len(S)
    i = 0
    j = size - 2
    while i < j:
        if S[i] != S[j]:
            return -1
        i += 1
        j -= 1

    # ここまで来た場合は必ず木を構築可能
    edges = []
    top = 0
    for i in range(size - 1):
        edges.append((top, i + 1))
        if S[i] == '1': 
            top = i + 1
    return edges

S = input()
ans = solve(S)
if ans == -1:
    print(ans)
else:
    for e in ans:
        print("{} {}".format(e[0] + 1, e[1] + 1))

Submission status: Accepted

Solution code:
s=input()
n=len(s)
if s[-1]=='1' or s[0]=='0':
    print(-1)
    exit()
for i in range(n-1):
    if s[i]!=s[-i-2]:
        print(-1)
        exit()
edges=[]
par=n
for i in range(n-1,0,-1):
    print(i,par)
    if s[i-1]=='1':
        par=i

Submission status: Accepted

Solution code:
S = input()
if S[0] == '0' or S[-1] == '1':
    print(-1)
    exit()
flag = True
for i in range((len(S)-1)//2):
    if S[i] != S[-2-i]:
        flag = False
        break
if not flag:
    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: Accepted

Solution code:
*S, = map(int, open(0).readline().strip())
N = len(S)
ok = 1
for i in range(N-1):
    if S[i] != S[-2-i]:
        ok = 0
        break
if not ok or S[0] != 1 or S[-1] != 0:
    print(-1)
    exit(0)

E = []
V = [i+1 for i in range(N//2) if S[i]]
p = 1
for v in V:
    for i in range(p, v):
        E.append("%d %d\n" % (i, v))
    p = v

E.append("%d %d\n" % (p, p+1))
p += 1
for i in range(p+1, N+1):
    E.append("%d %d\n" % (p, i))
open(1, 'w').writelines(E)

Submission status: Accepted

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:
    v = 1
    for i in range(N-1):
        print("{} {}".format(v, i+2))
        if s[i] == "1" and i+1 <= N//2:
            v = i + 2
        else:
            pass

Submission status: Accepted

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

s = input()
n = len(s)
if s[-1] == '1': die()
if s[0] == '0': die()
for i in range(n-1):
    if s[i] != s[-i-2]: die()

root = last = 1
for i in range(n-1):
    last+= 1
    print(root, last)
    if s[i] == '1': root = last

Submission status: Accepted

Solution code:
S = [int(x) for x in input()]
N = len(S)
if S[0] == 0 or S[-1] == 1 or any(S[i] != S[-i - 2] for i in range(N - 1)):
    print(-1)
    quit()

edge = [(1, 2)]
root, now = 2, 3
for i in range(1, N // 2 + 1):
    edge.append((root, now))
    if S[i] == 1:
        root = now
    now += 1
while now <= N:
    edge.append((root, now))
    now += 1
for s, t in edge:
    print(s, t)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
n = len(s)
comp = {i+1: True if st == '1' else False for i, st in enumerate(s)}
comp[0] = False

# feasibility check
feasible = True
for i in range(n//2 + 1):
    if i == 1 and not (comp[i] and comp[n-i]):
        feasible = False
        break
    elif comp[i] ^ comp[n-i]:
        feasible = False
        break

if not feasible:
    print(-1)
else:
    edge = []
    parent = n
    for i in reversed(range(1, n)):
        edge.append((i, parent))
        if comp[i]:
            parent = i
    for u, v in edge:
        print(u, v)

Submission status: Accepted

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=i+1
        else:
            print(c,i+2)
else:
    print(-1)

Submission status: Accepted

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[0] == '0':
    print(-1)
    exit()
elif 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: Accepted

Solution code:
def solve(s):
    if s[-1] == '1':
        return False
    if s[0] == '0':
        return False
    half = s[:len(s) // 2]
    if half != s[-2:(len(s) - 3) // 2:-1]:
        return False
    head = 1
    master = 1
    buf = []
    for i, c in enumerate(half):
        if c == '0':
            buf.append('{} {}'.format(master, i + 2))
        else:
            buf.append('{} {}'.format(head, i + 2))
            head = master = i + 2
    for i in range(len(half), len(s) - 1):
        buf.append('{} {}'.format(master, i + 2))
    return buf


res = solve(input())
if res == False:
    print(-1)
else:
    print('\n'.join(res))

Submission status: Accepted

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()
oya = n
for i in range(n-1,0,-1):
  ans.append([oya,i])
  if s[i-1] == "1":
    oya = i
for i in ans:
  print(*i)

Submission status: Accepted

Solution code:
s = input()
n,m,m2 = len(s),1,2
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,m2)
		if int(s[i]): m = m2
		m2+=1

Submission status: Accepted

Solution code:
s = input()
n = len(s)
if s[0] == '1' and s[-1] == '0' and s[:n//2] == s[(n-1)//2:-1][::-1]:
    q = []
    now = 0
    for i in range(n):
        m = s[i]
        if m == '1':
            now = str(i+1)
            while q:
                print( q.pop() + ' ' + now)
        q.append( str(i+1))
    while q:
        a = q.pop()
        if now != a:
            print( a + ' ' + now)
else:
    print(-1)

Submission status: Accepted

Solution code:
a=input()
b=a[:-1]
if a[0]=='0' or a[-1]=='1' or b!=b[::-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: Accepted

Solution code:
S = input()

L = len(S)
if S[0]=="0" or S[-1]=="1":
    print(-1)
    exit()
for i in range(L-2):
    if S[i] != S[L-2-i]:
        print(-1)
        exit()

pv = 1
for i in range(L-1):
    nv = i+2
    # 現頂点から次の頂点へ、長さを確保
    if S[i]=="1":
        print(pv,nv)
        pv = nv
    # 現頂点への葉とする
    else:
        print(pv,nv)

Submission status: Accepted

Solution code:
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('e1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    s = list(map(int, read_str()))
    n = len(s)
    if s[0] != 1:
        return -1
    if s[n - 1] != 0:
        return -1
    for i in range(n - 1):
        if s[i] != s[n - 2 - i]:
            return -1
    x = [i for i in range(n) if s[i] == 1]
    k = len(x)
    body = list(range(1, k + 2))
    res = [[body[i], body[i + 1]] for i in range(k)]
    p = k + 2
    for j in range(1, k):
        for l in range(x[j] - x[j-1] - 1):
            edge = [body[j], p]
            p += 1
            res.append(edge)
    return res


def main():
    res = solve()
    if res == -1:
        print(res)
        return
    for edge in res:
        print(*edge)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
n = len(s)
if s[-1] == '0' and s[0] == '1' and s[n - 2] == '1' and s[:n - 1] == s[n - 2 :: -1]:
    #s[i] = 「１辺を取り除いてi + 1頂点からなる連結成分を作れる」
    #連結成分のサイズは、1からn//2までチェックすれば十分
    #構成：各iに対し、iの次に1になっているbitを求める
    i = 0
    j = 1
    while j <= n - 2:
        if s[j] == '1':
            for k in range(i, j):
                print(k + 1, j + 1)
            i = j
            j = j + 1
        else:
            j += 1
    print(n - 1, n)

else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = lc()
n = len(s)

if s[0] == "0" or s[-1] == "1" or s[-2] == "0":
    print(-1)
    
elif s[:(n-1)//2] != s[n-2:n//2-1:-1]:
    print(-1)
    
else:
    par = n
    cur = n-1
    print(n,n-1)
    
    if n > 2:
        for si in s[-3::-1]:
            cur -= 1
            print(par,cur)
            if si == "1":
                par = cur

Submission status: Accepted

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

    q = collections.deque()
    for i in range(1,n):
        if s[i] == 1:
            q.append(i+1)
    q.append(n)
    c = 1
    r = []
    for i in range(1,n):
        if c == i:
            c = q.popleft()
        r.append('{} {}'.format(i,c))

    return '\n'.join(r)


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

S = S[:-1]
N = len(S)

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

pos = 2
print "1 2"
for i in range(1, N):
    print pos, i + 2
    if S[i] == '1':
        pos = i + 2