Pls tell me what does author of this problem mean..
If all delegates are in different rooms then we can't use less than 4 connections to achieve the goal in sample input. What 3 connections can we use to do it?
Do we need all M pairs to be in answer?
I still can't solve it because statement is too loose for me.

The line "every connection is made between people that can negotiate" actually means "a connection can only be made between two people that can negotiate".