Input 
4 1
3
1 2
2 3
2 4
Output 
2
1 4
Input 
8 3
6 5 7
1 5
5 4
5 3
1 6
2 7
1 2
1 8
Output 
4
2 3 4 8