Effective way to solve this problem

I have to do the program which takes from user:

n - number of elements

m - how many pairs the elements have

then user will write all pairs > 1 and 2; 1 and 3, ...

And output should the number which have the most elements >> where every element is in pair with all elements of that number.

for example: INPUT: 5 6 // n and m

1 2

1 3

1 4

1 5

3 2

4 2

OUTPUT: 1 2 3 or 4 1 2 (1 2 3 4 is not good because elements 3 and 4 aren't in pair)

(1 5 is also not good because 1 5 are in pair but they aren't the biggest)

I need to get this program working under 2 seconds with n = 100000 and m up to 300000

Is there some effective way to do it? I've tried to do it with all combinations and then I checked if all elements are in pair but it's not effective way (100 years to do it like that :D)

Sry for some english mistakes.

Re: Effective way to solve this problem

Your problem can be represented as a graph, where each pair is an edge. Then the problem is to find the largest connected component. I think you can find some efficient algorithms for that if you search a bit.