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