分数: 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.