Ariadna's blog is filled with delicious recipes and sensible advice for a healthy and balanced lifestyle. Unsurprisingly, it has thus gathered an impressive number of readers. This reader base is now stable, and Ariadna feels that it would be useful for them to interact more and form a tighter community, one that is not solely anchored to the blog.
Ariadna knows that some of the readers are already friends or acquaintances, and therefore have each other's email addresses. She thinks that a good start for developing the community would be for everyone to have everyone else's email address, so that everyone would be able to reach out to the entire group. Since she knows her blog's readers also greatly enjoy doing things in a "decentralized" fashion, she therefore devises the following protocol, to be started on day $$$D$$$:
You are a skillful hacker and you have managed to get access to all of the blog readers' address books. You would like to surprise and impress Ariadna by notifying her of whether or not the process she proposes will lead to everyone getting everyone else's address. Moreover, if the process is meant to succeed, you want to give her a good estimate of how many days it would take. More precisely, if the process succeeds, you can either give her:
The first line of the input contains two integers $$$N$$$ and $$$M$$$, corresponding to the number of readers and respectively to the number of pairs of readers that initially have each other's email address. Readers are numbered from $$$1$$$ to $$$N$$$.
The $$$M$$$ following lines each contain two integers, $$$i$$$ and $$$j$$$, meaning that readers $$$i$$$ and $$$j$$$ initially have each other's email address. Note that this means that both reader $$$i$$$ has reader $$$j$$$'s address and reader $$$j$$$ has reader $$$i$$$'s address.
Limits
The output should contain a single integer equal to either:
4 3 1 2 2 3 3 4
2
6 3 1 2 3 4 5 6
-1
Sample Explanation 1
The process proceeds as follows:
Название |
---|