Zju1015 Fishing Net弦图判定

给定一个连通图，将其看作一张鱼网。若鱼网中存在长度超过 $3$ 的闭合环，则该环必须存在一条弦，将其分成两个部分。这里，弦是指连接闭合环上两个不相邻结点，且不属于该环的边。

递归地看，这一条件等价于图中的每个网眼都只能是三角形。若鱼网满足上述条件，输出 Perfect；否则输出 Imperfect。

输入格式

输入数据仅包含一组测试数据。

第一行包含两个整数 $N$ 和 $M$，表示鱼网有 $N$ 个结点和 $M$ 条边。原题给出的结点数约束为 $N\le 0\le 1000$。

接下来 $M$ 行，每行包含两个整数 $A$ 和 $B$，表示结点 $A$ 与结点 $B$ 之间存在一条边。

输出格式

输出一行。

如果鱼网满足要求，输出 Perfect；否则输出 Imperfect。

样例输入

4 4
1 2
2 3
3 4
4 1

样例输出

Imperfect

样例解释

图中存在一个长度为 $4$ 的环 $1\to2\to3\to4\to1$，但环上不存在连接两个不相邻结点的弦，因此输出 Imperfect。

数据范围

• 原题给出的结点数约束为 $N\le 0\le 1000$。

来源与许可

本题为 ZJU 1015「Fishing Net」改编题，题面与测试数据整理自 BZOJ 1242。

样例 1

输入

4 4
1 2
2 3
3 4
4 1

输出

Imperfect