Python Programming Lab Dr.D has invented yet another invention: the hateinator. He wants to test it on a group of N people (numbered 1 through N). The hateinator may be used any number of times; to...

Python Programming Lab

Dr.D has invented yet another invention: the hateinator. He wants to test it on a group of N people (numbered 1 through N). The hateinator may be used any number of times; to use it once, Dr.D should divide these N people into two groups and press the fire button on the hateinator. We call each such grouping a Doofish set. Afterwards, there will be hatred between each two people who were in different groups. The hatred does not disappear ― any two people that hate each other before the hateinator is used still hate each other afterwards.

The hateinator uses a lot of power. Let's denote the number of times it is used by K. Then, it consumes K⋅N units of power. Dr.D cannot afford to use the hateinator if this number exceeds 106.

Dr.D has done the math and computed the most evil hatred system: a situation with some M pairs of people who hate each other. You are given these pairs. There must not be any other pair of people who hate each other. Initially, there is no hatred between these N people. Now, Dr.D is wondering: is it possible to use the hateinator to create this most evil system? If it is, what is the minimum number of times he needs to use it and with which Doofish sets? Help Dr.D find the answers. Develop a python code in not more than 100 lines to solve the problem. Below are some test cases for your assistance:

Input:

3 3

1 2

1 3

2 3

Output:

1

101