Input
3 2
1 2
2 3
1 1 1
Output
3
1 2 3
Input
5 7
1 2
1 3
1 4
1 5
3 4
3 5
4 5
0 1 0 1 0
Output
10
2 1 3 4 5 4 5 4 3 1
Input
2 0
0 0
Output
0