Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:512 MB

#1007. 仙人掌

统计

给定n个整数d1,d2,……,dn 。构造具有n个顶点的仙人掌,使得顶点i的度数刚好为di ,或者确定不 存在这样的仙人掌。平行的边和环不允许。
输入格式
第一行包含一个整数n(2≤n≤2000 )~--- 仙人掌中的顶点数。
第二行包含n个整数d1,d2,……,dn (1≤di≤n-1 )~--- 所需的顶点度数。
输出格式
如果无法构建满足条件的仙人掌,则输出单个整数-1 。
否则,按照传统,将构建的仙人掌输出为一组边不同的路径。
在第一行输出一个整数m --- 此类路径的数量。以下每一行m都应包含图中的路径。路径应以整数Ki(Ki≥2) 开头,后跟Ki整数,从1 到 n。这些Ki整数应该代表这条路径的连续顶点。路径中的相邻顶点应该是不同的。路径可以多次访问同一个顶点,但在整个输出中应该只遍历仙人掌的每条边一次。
样例

input
5
2 2 3 2 1 
output
4
2 1 2 
2 2 3 
2 3 1 
3 3 4 5
样例1解释
1.png

input
4
3 3 2 2
output
-1
input
6
1 2 1 1 2 1
output
-1
input
15
1 4 3 2 2 2 2 2 4 4 2 2 2 2 2
output
3
9 1 2 3 4 5 6 7 8 3 
7 2 9 10 11 12 13 10 
5 2 14 9 15 10
样例4解释

2.png
数据范围 对于25% 的数据,∀i,di=2
对于100%的数据,2≤n≤2000