E - Tr/ee Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ n の文字列 s が与えられます。 以下の条件を満たす n 頂点の木は存在するでしょうか？

  • 各頂点には 1,2,..., n の番号が付けられている
  • 各辺には 1,2,..., n-1 の番号が付けられていて、i 番目の辺は 頂点 u_i と v_i をつないでいる
  • s の i 番目の文字が 1 であるとき、 木からある辺を 1 つ取り除くことで、サイズ i の連結成分が作れる
  • s の i 番目の文字が 0 であるとき、 木からどのように辺を 1 つ取り除いてもサイズ i の連結成分が作れない

条件を満たす木が存在する場合、1 つ構築してください。

制約

  • 2\leq n \leq 10^5
  • s は 0 と 1 からなる長さ n の文字列

入力

入力は以下の形式で標準入力から与えられる。

s

出力

条件を満たす n 頂点の木が存在しない場合、-1 と出力してください。

条件を満たす n 頂点の木が存在する場合、 n-1 行出力してください。 i 行目には u_i,v_i を空白区切りで出力してください。 複数の木が条件を満たす場合、どれを出力しても構いません。

入力例 1

1111

出力例 1

-1

n 頂点の木から辺を 1 つ取り除いてサイズ n の連結成分を作ることはできません。

入力例 2

1110

出力例 2

1 2
2 3
3 4

1 番目の辺または 3 番目の辺を取り除くと、サイズ 1 の連結成分とサイズ 3 の連結成分ができます。 2 番目の辺を取り除くと、サイズ 2 の連結成分が 2 つできます。

入力例 3

1010

出力例 3

1 2
1 3
1 4

どの辺を取り除いても、サイズ 1 の連結成分とサイズ 3 の連結成分ができます。

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.