You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Sample Input

input1:

4 1

1 2

2 3

3 4

2 4

input2:

7 2

1 2

1 3

4 2

2 5

6 5

5 7

1 7

2 6

input3:

4 3

1 2

1 3

1 4

2 3

2 4

3 4

Sample Output

output1:

4

output2:

8

output3:

0