|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||512 MB||35||15||7||33.333%|
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$:
If a person does not need to do any update at 8pm, then the process is said to have converged for this person, and she will no longer need to continue sending emails over the next days.
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.
The output should contain a single integer equal to either:
4 3 1 2 2 3 3 4
The process proceeds as follows:
The last update takes place on day $D$+1, after 2 elapsed days. The process has converged for everyone on day $D$+2, after 3 elapsed days. The sample output contains the former value, 2. Outputting the latter value, 3, is an equally correct alternative.
6 3 1 2 3 4 5 6