和平集会总顾问 (GCPC) 的工作非常繁重。几乎每天都有人来找他们，要求组织一场参会者之间不太和睦的会议。更具体地说，在任何参会者群体中，可能存在几对互相厌恶的人。尽管如此，人们有时仍需要会面，因此 GCPC 的通用策略是将参会者分成两组。这两组人将在不同的房间开会，GCPC 的员工会在两个房间之间来回传递信息。我们姑且称这两个房间为东房间和西房间——没有特别的原因。为了确保会议和平且富有成效，GCPC 将人员分配到东房间和西房间，使得每个房间内没有两个人互相厌恶。

随着时间的推移，将人员分配到东房间和西房间的过程变得有些繁琐，因此你决定进行一个小实验。一些 GCPC 的客户每年都会安排完全相同的人员参加同一场会议。为了保持趣味性，你希望每次会议都使用一种新的分配方式。如果会议的届数从 1 开始编号，那么你被迫重复使用之前已经用过的分配方式的第一场会议是第几届？注意，仅仅交换房间，即把东房间的人分配到西房间，反之亦然，并不被视为一种不同的分配方式——毕竟，还是同样的人在会面。由于你的调查几乎肯定只具有学术性质，你对确切的数值不感兴趣。只需找到结果除以给定的奇素数 $p$ 后的余数即可。

输入格式

输入包含： 一行，包含三个整数 $n, m$ 和 $p$ ($1 \le n \le 10^6, 0 \le m \le 10^6, 3 \le p \le 10^9$)，其中 $n$ 是参会人数，$m$ 是他们之间已知的厌恶关系数量，$p$ 是一个奇素数。参会者编号从 $1$ 到 $n$。 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，表示参会者 $a$ 和 $b$ 互相厌恶。

输出格式

输出一个整数，表示必须重复分配方式的第一届会议的编号。输出该编号对 $p$ 取模的结果。如果无法将人员分配到东房间和西房间，使得没有两个互相厌恶的人被放在同一个房间，则输出 impossible。

样例

样例输入 1

4 2 11
1 2
3 4

样例输出 1

3

样例输入 2

5 2 3
1 2
3 4

样例输出 2

2

样例输入 3

3 3 11
1 2
2 3
3 1

样例输出 3

impossible

样例输入 4

100 0 13

样例输出 4

9

说明

在第一个样例中，你可以使用以下房间分配方式：

在第三年，分组情况与第一年相同，且不存在比这更长的避免重复的分配方案。

在第二个样例中，一种最优的分配方案如下：