test 1 failed.
Input:
5 2
1 2
2 3
1 4
1 5
5 1 3 4
Expected: 1
1
1 5 1
4 3 1
Got: 1
1
1 4 1
3 5 1