J. Joint Excavation
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
3 2
3 1
2 1
Output
1 1
1 
2 
3
Input
4 3
1 3
2 3
3 4
Output
2 1
1 3 
4 
2
Input
7 7
1 2
2 3
4 2
2 5
4 5
6 7
7 2
Output
3 2
1 2 4 
6 7 
3 5