8
1 2
1 2
3 4
4 5
3 4
1 2
3 4
1 2

Answer 2 p.s. Greedy Algorithm leads to AC