A graph Problem

[conantth]

Hi guys!
I have got a very interesting problem ... well for me it's hard....

An undirect graph G. N (N<=300) vertices and M (M<=N*(N+1)/2) edges (i connects to j means j connects to i);.. It's a connected graph!... There's a positive K>0..
The problem is choose k edge(s) and delete them from the graph that makes the graph divided into 2 connected parts. X is the group verteces of the part 1 and Y is the verteces of part 2, vertex 1 must be in X and vertex n must be in Y. We have to choose k edges that makes abs(X-Y) smallest..
There's always have at leat 1 solution!
For example:
6 8 4 {n and m)
1 2
1 3
1 4
1 5
2 6
3 6
4 6
5 6
output
2 6
3 6
1 4
1 5
{X=3 and Y=3 Abs(X-Y)=0 }

Help me as soon as posible!