1303 - 长度为K的路径数量2
Description

现在有一个简单的连通图,尝试输出,从任意号点出发,长度为K路径数量

并输出路径的访问点属性

点的编号是1~n

n<=100


Input

两个数字N和M

接下来M行代表联通

倒数第一行一个数字q表示长度为q的路径数量


Output

前面k行,路径的情况

最后一行,一个数字cnt,表示路径的数量


Examples

Input

3 3
1 2
2 3
1 3
2

Output

1->2
1->3
2->1
2->3
3->1
3->2
6
Hint

注意是字典序,也就是起点也是从小到大去枚举

1->2
1->3
2->1
2->3
3->1
3->2

因为起点不固定,从任意一个点出发,长度为2的路径数量一共为6条

按顺序遍历点,点的编号从1开始


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 95
通过次数 51