25255번 - Killjoys' Conference 다국어

The General Counsel for Peaceful Congregations (GCPC) has a very, very stressful job. Almost every day they are approached by someone who has to organise a meeting whose attendees do not really get along. More specifically, in any group of attendees there may be several pairs of people who are known to dislike each other. Nevertheless people sometimes need to meet, so the general strategy of the GCPC is to split up the meeting attendees into two groups. These groups will then meet in different rooms and GCPC employees will deliver messages back and forth between the two rooms. Let's call these two rooms the East and the West room -- for no particular reason. To ensure peaceful and productive meetings, the GCPC assigns people to the East and West room such that no two people in each room dislike each other.

Over time, the process of assigning people to the East and West rooms has become a bit tedious, so you decided to undertake a little experiment. Some of the GCPC's clients schedule the same meeting with the exact same people every year. To keep things interesting, you want to use a new assignment of people to the East and West rooms for each meeting. If the editions of the meeting are numbered starting from $1$, what is the number of the first meeting where you are forced to reuse an assignment of people that you have already used before? Note that simply swapping the rooms, i.e.\ assigning the people from the East room to the West room and vice versa, is not considered a different assignment -- after all, the same people will meet. Since your investigation will almost certainly only be of an academic nature, you are not interested in the exact value. It will suffice to find the remainder when dividing the result by a given odd prime number $p$.

The input consists of:

• One line with three integers $n$, $m$ and $p$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$, $3 \le p \le 10^9$), where $n$ is the number of people attending the meeting, $m$ is the number of known dislikes between them and $p$ is an odd prime number. The attendees of the meeting are numbered from $1$ to $n$, inclusive.
• $m$ lines, each with two integers $a$ and $b$ ($1 \le a,b \le n, a \neq b$), specifying that attendees $a$ and $b$ dislike each other.

Output one integer, the number of the first edition where an assignment must re-occur. Output this number modulo $p$. If it is impossible to assign the people to the East and West rooms such that no two people disliking each other are placed in the same room, output impossible.

In the first sample, you could use the following room assignments:

In the third year the groups are the same as in the first year, and there is no set of assignments that avoids repetitions this for longer than that.

In the second sample, an optimal set of assignments is given as follows: