number of vertices :  9 
number of required edges  7 
1 2 2 2 6
1 3 3 3 3
2 3 1 1 2
4 5 1 1 3
5 6 2 2 3
6 7 2 2 6
8 9 3 3 7
number of non required edges  7 
1 9 3 3 0
3 4 1 1 0
3 8 3 3 0
3 9 3 3 2
4 7 1 1 0
6 8 5 5 1
6 9 5 5 3
