number of vertices :  19 
number of required edges  17 
1 2 3 3 9
2 3 1 1 1
2 4 5 5 10
3 4 4 4 12
5 6 2 2 3
5 8 4 4 12
6 7 6 6 14
7 8 3 3 3
7 9 1 1 2
8 9 5 5 7
10 11 2 2 6
10 12 3 3 4
13 14 6 6 10
14 15 4 4 11
14 16 3 3 5
17 18 9 9 14
18 19 2 2 3
number of non required edges  27 
1 19 7 7 0
3 5 7 7 4
3 6 8 8 5
3 14 5 5 4
3 17 5 5 4
4 14 6 6 3
4 17 6 6 4
4 19 13 13 5
5 13 9 9 4
5 14 7 7 2
6 14 8 8 4
8 13 6 6 0
9 10 4 4 1
9 12 5 5 1
9 15 10 10 0
9 16 10 10 5
9 17 16 16 11
11 12 4 4 3
11 16 14 14 12
11 17 20 20 12
12 16 13 13 7
12 17 19 19 17
13 15 4 4 0
14 17 6 6 4
14 19 13 13 11
15 16 5 5 1
17 19 10 10 1
