20
9 13
12 14
12 19
12 20
13 18
13 20
17 20
18 20
//ans: 6

20
2 6
2 8
3 13
3 15
3 16
3 17
6 11
6 12
6 13
6 15
6 18
8 11
9 13
11 14
11 16
11 18
12 14
12 19
13 18
15 16
//ans: 14

10
1 4
1 6
1 8
4 10
4 3
3 7
4 6
6 2
2 5
5 9
//ans: 10

8
1 2
2 3
1 3
1 4
1 5
//ans: 4

4
1 2
1 3
1 4
2 3
//ans: 4

10
10 9
10 2
10 1
9 6
9 5
8 7
8 2
8 1
7 4
7 3
6 5
6 3
4 3
//ans: 10

10
1 2
1 9
1 10
2 5
2 6
3 4
3 9
3 10
4 7
4 8
5 6
5 8
7 8
//ans: 10

8
1 2
1 3
1 6
2 3
2 4
4 7
4 8
5 6
5 7
//ans: 8

8
1 2
1 7
1 8
2 5
2 6
3 4
3 7
4 5
5 6
//ans: 8

16
1 7
2 4
2 5
3 15
4 5
5 12
5 13
6 14
6 16
8 12
8 14
9 10
9 15
11 15
13 14
//ans: 14

5
1 2
2 3
3 4
3 5
1 5
//ans: 4

6
1 2
2 3
1 3
3 4
2 5
5 6
//ans: 6

5
1 2
2 3
1 3
3 4
2 5
//ans: 4

3
1 2
2 3
1 3
//ans: 3

10
1 2
2 3
3 5
2 4
9 10
//ans: 6

4
1 2
2 3
1 3
1 4
//ans: 4

5
1 2
1 3
1 4
1 5
//ans: 2

5
1 2
1 3
1 4
1 5
5 2
//ans: 4

And the test against the greed algorithm.
10
1 2
1 3
2 3
2 4
1 4
3 4
3 5
5 6
6 7
6 8
6 9
6 10
7 8
7 9
7 10
8 9
8 10
9 10
//ans: 10

ans:3
??