8727: BZOJ4727:[POI2017]Turysta

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给出一个n个点的有向图,任意两个点之间有且仅一条有向边。对于每个点v,求出从v出发的一条经过点数最多, 且没有重复经过同一个点两次以上的简单路径。


输入格式

第一行包含一个正整数n(2<=n<=2000),表示点数。接下来n-1行,其中的第i行有i-1个数,如果第j个数是1,那么 表示有向边j->i+1,如果是0,那么表示有向边j<-i+1。


输出格式

输出n行,第i行首先包含一个正整数k,表示从i点出发的最优路径所经过的点数,接下来k个正整数,依次表示路 径上的每个点。若有多组最优解,输出任意一组。


样例输入

4
1
1 1
1 0 1

样例输出

4 1 2 3 4
3 2 3 4
3 3 4 2
3 4 2 3

提示

没有写明提示


题目来源

鸣谢Claris上传

加入题单

上一题 下一题 算法标签: