← 返回题目列表

AtCoder · arc103_c

E. 树形分割

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你一个字符串 s 长度 n。 一棵树有 n 满足以下条件的顶点存在吗?

  • 顶点已编号 1,2,..., n.
  • 边缘已编号 1,2,..., n-1和边缘 i 连接顶点 u_i 和 v_i.
  • 如果 i- 第一个字符 s is 1,我们可以有一个大小为 i 通过从树中删除一条边。
  • 如果 i- 第一个字符 s is 0,我们不能有大小的连接组件 i 通过从树中删除任何一条边。

如果存在这样的树,则构造一棵这样的树。

约束

  • 2 \leq n \leq 10^5
  • s 是一个长度为的字符串 n 组成 0 和 1.

输入

输入由标准输入按以下格式给出:

s

输出

如果一棵树 n 满足条件的顶点不存在,打印 -1.

如果一棵树 n 满足条件的顶点存在,打印 n-1 行。 的 i- 第行应包含 u_i 和 v_i 之间有一个空格。 如果有多棵树满足条件,则任何这样的树都将被接受。


示例输入 1

1111

示例输出 1

-1

不可能有大小相同的连通分量 n 从树中删除一条边后 n 顶点。


示例输入 2

1110

示例输出 2

1 2
2 3
3 4

如果边缘 1 或边缘 3 被删除,我们将有一个大小为的连接组件 1 和另一个尺寸 3。如果边缘 2 被删除,我们将有两个连接的组件,每个组件的大小 2.


示例输入 3

1010

示例输出 3

1 2
1 3
1 4

删除任何边将产生大小为 1 和另一个尺寸 3.