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:
def check(S):
    size = len(S)
    if S[0]=="0" or S[-1]=="1":
        return False
    else:
        for i in range(size-1):
            a, b = i, size-i-2
            if (S[a]=="1" and S[b]=="0") or (S[a]=="0" and S[b]=="1"):
                return False
        return True


S = input()
if check(S):
    N = len(S)
    l = [1]
    p = False
    for i in range(2, N+1):
        if p:
            l.append(i)
        else:
            print(l[-1], i)
        p = (S[i-1]=="1")
    for i in range(len(l)-1):
        print(l[i], l[i+1])
else:
    print(-1)

Submission status: Accepted

Solution code:
S = input()

def check(S):
    size = len(S)
    if S[0]=="0" or S[-1]=="1":
        return False
    else:
        for i in range(size-1):
            a, b = i, size-i-2
            if (S[a]=="1" and S[b]=="0") or (S[a]=="0" and S[b]=="1"):
                return False
        return True

if check(S):
    N = len(S)
    l = [1]
    p = False
    for i in range(2, N+1):
        if p:
            l.append(i)
            if S[i-1]=="1":
                p = True
            else:
                p = False
        else:
            print(l[-1], i)
            if S[i-1]=="1":
                p = True
    sl = len(l)
    for i in range(sl-1):
        print(l[i], l[i+1])
else:
    print(-1)

Submission status: Accepted

Solution code:
s=input()
if s[0]=='0' or s[-1]=='1' or s[:-1]!=s[:-1][::-1]:
    print(-1)
    exit(0)
e=[]
bi=0
for i,j in enumerate(s[:-1]):
    e.append([bi,i+1])
    if j=='1':
        bi=i+1
for i,j in e:
    print(i+1,j+1)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

s = input()
n = len(s)
if s[0]=="0" or s[-2]=="0" or s[-1]=="1":
    print("-1")
elif any(s[i]!=s[-2-i] for i in range(n-1)):
    print("-1")
else:
    i = 1
    ps = set([i])
    es = []
    for c in s[1:]:
        i += 1
        if c=="0":
            ps.add(i)
        else:
            for u in ps:
                es.append("%s %s" % (u,i))
            ps = set([i])
    for u in ps:
        if u!=n:
            es.append("%s %s" % (u, n))
    write("\n".join(es))

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
if s[n - 1] == "1" or s[0] == "0":
    print(-1)
    exit()
for i in range((n - 1) // 2):
    if not s[i] == s[n - 2 - i]:
        print(-1)
        exit()
l = n - s.count("0") + 1
x = [0] * l
j = 0
for i in range(n // 2):
    if s[i] == "1":
        j += 1
    else:
        x[j] += 1
        x[l - 1 - j] += 1
        if j == l - 1 - j and n % 2 == 0 and i == (n - 1) // 2:
            x[j] -= 1
for i in range(l - 1):
    print(i + 1, i + 2)
k = n - s.count("0") + 2
for i in range(l):
    for _ in range(x[i]):
        print(i + 1, k)
        k += 1

Submission status: Accepted

Solution code:
s = input()

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

edges = []
head = 0
for idx, i in enumerate(s[:-1]):
    edges.append([head, idx + 1])
    if i == '1':
        head = idx + 1
for i, j in edges:
    print(i + 1, j + 1)

Submission status: Accepted

Solution code:
def main():
    S = list(input())

    N = len(S)

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

    lst = []
    for i in range((N - 1) // 2):
        if S[i] != S[N - 2 - i]:
            print (-1)
            return 0
        if S[i] == '1':
            lst.append(i + 1)
    if N % 2 == 0 and S[N//2 - 1] == '1':
        lst.append(N//2)
    # print (lst)

    if lst[-1] * 2 != N:
        center = lst[-1] + 1
        for x in range(lst[-1] * 2 + 2, N + 1):
            print (center, x)

        before = 1
        n = lst[-1] * 2 + 2
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, center)
        print (n - tmp, center)

    if lst[-1] * 2 == N:
        before = 1
        n = lst[-1] * 2 + 1
        tmp = 1
        for tmp in lst[1:]:
            print (before, tmp)
            print (n - before, n - tmp)
            for x in range(tmp - before - 1):
                print (before + 1 + x, tmp)
                print (n - (before + 1 + x), n - tmp)
            before = tmp
        print (tmp, n - tmp)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    if S[0] == "0" or S[-1] == "1":
        return []

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

    res = []
    path = S.count("1")
    for i in range(1, path + 1):
        res.append((i, i + 1))

    u = len(res) + 1
    v = 1
    for s in S[:-1]:
        if s == "1":
            v += 1
        else:
            u += 1
            res.append((v, u))

    return res


if __name__ == "__main__":
    tree = Tree()
    if tree:
        for x, y in tree:
            print(x, y)
    else:
        print(-1)

Submission status: Accepted

Solution code:
def no():
    print(-1)
    exit()


s = input()
n = len(s)

if s[-1] == "1":
    no()

s = s[:-1]

if s != s[::-1]:
    no()

if s[0] == "0":
    no()

li = [0]
adj = [[] for _ in range(n + 1)]
for v, e in enumerate(s, 1):
    if e == "1":
        for u in li:
            adj[u].append(v)
        li = []

    li.append(v)

adj[n-1].append(n)

for u, vs in enumerate(adj[1:], 1):
    for v in vs:
        print(u, v)

Submission status: Accepted

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

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

data=[]
for i in range(0,n-1):
    if s[i]=="1":
        data.append(i+1)
        if s[n-2-i]=="0":
            print(-1)
            exit()
m=len(data)
edge=[]
for i in range(1,m):
    edge.append((i,i+1))
index=m+1
for i in range(1,m):
    if i!=1:
        size=data[-i]
        nextsize=data[-i-1]
        E=size-1-nextsize
        count=0
        while E>count:
            edge.append((i,index))
            index+=1
            count+=1
    else:
        size=n
        nextsize=data[-2]
        E=size-1-nextsize
        count=0
        while E>count:
            edge.append((i,index))
            index+=1
            count+=1

for i in range(n-1):
    u,v=edge[i]
    print(u,v)

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[-i-2]:print(-1);exit()
b=[]
for i in range(n-1):
  if s[i]=="1":
    for j in b:print(j+1,i+1)
    b=[]
  b.append(i)
for j in b:print(j+1,n)

Submission status: Accepted

Solution code:
s=input()
if s[0]=='0':
  print(-1)
elif s[-1]=='1':
  print(-1)
else:
  l=len(s)
  for i in range(l-1):
    if s[i]!=s[l-i-2]:
      print(-1)
      exit()
  ans=[]
  base=1
  for i in range(l-1):
    if s[i]=='1':
      print(base,i+2)
      base=i+2
    else:
      print(base,i+2)

Submission status: Accepted

Solution code:
s = list(map(int, input()))
n = len(s)
if s[0]==0 or s[-1] == 1 or any(s[i]!=s[i] for i in range(n//2)):
    print(-1)
    exit()
G = [[] for i in range(n)]
cur = 0
for i in range(n-1):
    G[cur].append(i+1)
    G[i+1].append(cur)

    if s[i]:
        cur = i+1

root = n//2
from collections import deque
size = [1]*n
ans = [0]*n
edges = []
def bfs1(root):
    rev = [(root, -1)]
    for i in range(n):
        cur, par = rev[i]
        for to in G[cur]:
            if to != par:
                rev.append((to, cur))
    for i in reversed(range(1,n)):
        cur, par = rev[i]
        size[par] += size[cur]
        ans[size[cur]] = 1
        ans[n-size[cur]] = 1
        edges.append([cur+1, par+1])
bfs1(0)

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

for i in edges:
    print(*i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

dfs(N)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

edges = []
base = 1
for i in range(1, N):
    edges.append((base, i+1))
    if S[i] == '1':
        base = i + 1
[print(*edge) for edge in  edges]

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

s = list(input())
n = len(s)

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

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

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

from_ = 1
to_ = 2
ans = []
for i in range(n-1):
    ans.append((from_,to_))
    if s[i] == '1':
        from_ = to_
        to_ += 1
    else:
        to_ += 1

for a in ans:
    print(*a)

Submission status: Accepted

Solution code:
S = input()
n = len(S)
m = n // 2
if S[0] == '0' or S[-1] == '1':
  print(-1)
  quit()

ans = [[1, 2]]
node = 1
now = 3
for i in range(m):
  if S[i] != S[n-i-2]:
    print(-1)
    quit()
  else:
    if i == 0:
      continue
    ans.append([node, now])
    if S[i] == '0':
      now += 1
    else:
      node = now
      now += 1

for i in range(now, n+1):
  ans.append([node, i])

for a in ans:
  print(*a)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
n = len(s)
s = '0'+s
if s[1]=='0' or s[n]=='1':
    print(-1)
    exit()
for i in range(1,n):
    if s[i]!=s[n-i]:
        print(-1)
        exit()
e = []
p = 1
for i in range(2,n+1):
    if s[i]=='1' or i==n:
        for j in range(p,i):
            e.append((j,i))
        p = i
for z in e:
    print("{} {}".format(z[0],z[1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#01:36
s = input()
n = len(s)
if s[-1] == '1':
  print(-1)
  exit()
t = s[:-1]
if t[::-1] != t:
  print(-1)
  exit()
if s[0] == '0':
  print(-1)
  exit()
print(0+1,1+1)
now = 0
for i in range(2,n):
  print(now+1,i+1)
  if s[i-1] == '1':
    now = i

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = '-' + sr()
N = len(S) - 1

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

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

# 42

Submission status: Accepted

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

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

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = '-' + sr()
N = len(S) - 1
def solve(S):
    if S[1] == '0':
        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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = list(sr())
N = len(S)
if S[-1] == '1' or S[0] == '0' or S[:-1] != S[:-1][::-1]:
    print(-1); exit()
S = ['-'] + S

def solve(S):
    prev = 1
    graph = []
    for i in range(1, N//2 + 1):
        if S[i] == '0':
            continue
        for x in range(prev, i):
            print(x, i)
        prev = i
    for x in range(prev, N):
        print(x, N)

graph = solve(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_right
s = list(map(int,list(input())))
s.insert(0,-1)
n = len(s)-1
flag = 0
if s[n]==1 or s[1]==0 or s[n-1]==0:
    flag = 1
else:
    for i in range(2,n-1):
        if s[i]!=s[n-i]:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    print(n,n-1)
    A = [1,n-1]
    cur = 1
    for i in range(2,n-1):
        if s[i]==1:
            print(cur,i)
            cur = i
            A.append(i)
    print(cur,n-1)
    A = sorted(A)
    for i in range(2,n-1):
        if s[i]==0:
            ind = bisect_right(A,i)
            print(i,A[ind])

Submission status: Accepted

Solution code:
def main():
    s=input()
    n=len(s)
    res = []
    if s[0]=="0" or s[-1] == "1":
        print(-1)
        return 1
    m=n//2
    t=m
    for i in range(m,0,-1):
        if s[i-1] != s[n-i-1]:
            print(-1)
            return 1
        if i == m:
            if s[i-1]=="1":
                res.append([m,m+1])
                for j in range(m+2,n+1):
                    res.append([m+1,j])
            else:
                for j in range(m+1,n+1):
                    res.append([m,j])
        else:
            if s[i-1]=="1":
                res.append([t,i])
                t=i
            else:
                res.append([t,i])
    for sres in res:
        print(" ".join(map(str, sres)))


main()

Submission status: Accepted

Solution code:
import sys

s=list(map(int,list(input())))
n=len(s)
if s[0]==0 or s[-1]==1:
    print(-1)
    sys.exit()
for i in range(n//2):
    if s[i]==s[n-2-i]:
        continue
    else:
        print(-1)
        sys.exit()
ans=[[1,2]]
last_edge=2
for i in range(3,n+1):
    ans.append([last_edge,i])
    if s[i-2]==1:
        last_edge=i
for u in ans:
    print(*u)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    N = len(S)
    if S[N-1] == '1':
        print(-1)
        return -1

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

    if S[N-2] != '1':
        print(-1)
        return -1


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

    p = [N]
    for i in range(N, 0, -1):
        if S[i-1] == '1':
            p.append(i)
        else:
            p.append(p[-1])
    p.reverse()
    e = []
    for i in range(1, N):
        e.append((i, p[i]))

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = '0'
s += input()


def isPara(string, l, r):
    while l <= r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True


def solve():
    N = len(s)-1
    if s[N] == '1' or s[1] == '0':
        print(-1)
        return
    if isPara(s, 1, N-1) == False:
        print(-1)
        return
    root = 1
    for i in range(2, N+1):
        print(str(root) + ' ' + str(i))
        if s[i-1] == '1':
            root = i


solve()

Submission status: Accepted

Solution code:
s = '0'
s += input()


def isPara(string, l, r):
    while l <= r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True


def solve():
    N = len(s)-1
    if s[N] == '1' or s[1] == '0':
        print(-1)
        return
    if isPara(s, 1, N-1) == False:
        print(-1)
        return
    sz = 1
    while sz < N:
        if(s[sz] == '1'):
            sz += 1
        else:
            break
    sz -= 1
    # a max chain of sz
    now = 1
    for i in range(2, N+1):
        print(str(now) + ' ' + str(i))
        if(s[i-1] == '1'):
            now = i


solve()

Submission status: Accepted

Solution code:
s = input()

N = len(s)

flag=True
if s[N-1]=='1':
        flag=False
if s[0]=='0' or s[N-2]=='0':
        flag=False


for i in range(N//2):
        if s[i]!=s[N-i-2]:
                flag=False
                break

if flag:
        ans = []
        prev = 0
        for i in range(N//2):
                if s[i]=='1':
                        for j in range(prev,i):
                                ans.append([i+1,j+1])
                        prev = i
        
        for i in range(prev,N-1):
                ans.append([N,i+1])
        
        for a in ans:
                print(*a)
else:
        print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    S=[None]+list(map(int,input()))
    n=len(S)-1

    # check
    if(not (S[1]==1 and S[n-1]==1)):
        print(-1)
        return
    if(S[n]==1):
        print(-1)
        return
    if(any(S[i]!=S[n-i] for i in range(1,n-1))):
        print(-1)
        return

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

Submission status: Accepted

Solution code:
S = input()
T = S[:-1]

if S[0] == "0" or S[-1] == '1' or T != T[::-1]:
    print(-1)
    quit()

u = 1
for v in range(2, len(S) + 1):
   print(u, v)
   if S[v - 2] == '1':
       u = v

Submission status: Accepted

Solution code:
def main():
    s=input()
    n=len(s)
    if s[n-1]=="1" or s[0]=="0":
        print(-1)
        return 0
    for i in range(n//2):
        if s[i]!=s[n-i-2]:
            print(-1)
            return 0
    t=[]
    now=1
    for i in range(n//2-1):
        t.append([now,i+2])
        if s[i]=="1":
            now=i+2
    t2=[[i+n//2,j+n//2] for i,j in t]
    if s[n//2-1]=="1":
        t.append([now,now+n//2])
    else:
        for i in range(len(t2)):
            if t2[i][0]==now+n//2:
                t2[i][0]=now
            if t2[i][1]==now+n//2:
                t2[i][1]=now
        t.append([now,now+n//2])
    if n%2==1:
        t.append([now,n])
    t+=t2
    for i,j in t:
        print(i,j)
main()

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	s = list(input())
	N = len(s)
	judge = "Yes"
	if s[0] == "0":
		judge = "No"
	if s[N - 1] == "1":
		judge = "No"
	for i in range(N - 2):
		if s[i] != s[N - 2 - i]:
			judge = "No"
	if judge == "No":
		print(-1)
		return

	c = 1
	d = N
	for i in range(N - 1):
		if s[i] == "1":
			print(c, c + 1)
			c += 1
		else:
			print(c, d)
			d -= 1

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
s = [int(i) for i in input()]
    
if s[0] == 0 or s[-1] == 1 :
    print(-1)
    
else :
    s.pop()
    if s != s[::-1] :
        print(-1)
        
    else :
        org = 1
        for i in range((len(s) + 1) // 2) :
            if s[i] == 1 :
                for j in range(org + 1, i + 3) :
                    print(org, j)
                org = i + 2
        for i in range(org + 1, len(s) + 2) :
            print(org, i)

Submission status: Accepted

Solution code:
import sys
S = input()
N = len(S)
ss = S[:N-1]
if S[-1] == '1' or ss != ss[::-1] or S[0] == '0':
    print(-1)
    sys.exit()
tree = []
cnt = 0
for s in ss:
    if s == '1':
        tree.append(cnt)
        cnt = 0
    else:
        cnt += 1
ans = []
now = 1
for c in tree:
    for i in range(c):
        ans.append((now, now+i+1))
    ans.append((now, now+c+1))
    now = now+c+1
for a, b in ans:
    print(a, b)

Submission status: Accepted

Solution code:
import sys

s = input()

num = len(s)

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

s = s[:-1]

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

lis = []
ans = []

for i in range(num-1):

    if i != 0 and s[i] == "1":
        lis.append(i+1)

#print (lis)

now = 1
for i in range(len(lis)):

    while now < lis[i]:
        ans.append([now,lis[i]])
        now += 1

    if i != len(lis)-1:
        ans.append([lis[i],lis[i+1]])
        now += 1

ans.append([num-1,num])


for i in ans:
    print (i[0],i[1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = list(map(int, list(input())[: -1]))
if s[0] == 0 or s[-1] == 1:
  print(-1)
  exit(0)
n = len(s)
for i in range(n - 1):
  if s[i] != s[-2 - i]:
    print(-1)
    exit(0)
res = []
temp = []
s[-1] = 1
for i in range(n):
  if s[i] == 0 or i == 0:
    temp.append(i + 1)
  else:
    if len(res):
      p = res[-1][0]
      res.append((i + 1, p))
    if len(temp):
      while len(temp):
        res.append((i + 1, temp.pop()))
for _ in range(len(res)):
  print(*res.pop())

Submission status: Accepted

Solution code:
s = input()
n = len(s)
if s[0] == '0':
    print(-1)
    exit(0)
if s[-1] == '1':
    print(-1)
    exit(0)
for i in range((n - 1) // 2):
    if s[i] != s[n - i - 2]:
        print(-1)
        exit(0)
p = 1
t = 2
i = n - 2
while i >= 0:
    print(p, t)
    if s[i] == '1':
        p = t
    t += 1
    i -= 1

Submission status: Accepted

Solution code:
S = [int(a) for a in list(input())]
L = len(S)

ok = True
if S[L-1] == 1 or S[0] == 0 or S[L-2] == 0:
    ok = False
for i in range(L-1):
    if S[i] != S[L-2-i]:
        ok = False

if not ok:
    print(-1)
else:
    graph = []
    p = 1
    go = True
    for i in range(1, L):
        if i <= L//2:
            graph.append((p, i+1))
            if go:
                p = i+1
            if S[i] == 1:            
                go = True
            else:
                go = False
        else:
            graph.append((p, i+1))
    
    for a, b in graph:
        print(a, b)