FISHNET - Fishing Net

题意翻译

# 题目描述 在一个高度现代化的渔村,居民们以渔业为生。 他们的主要工具——渔网,由计算机生产和修复。 他们每次出海都满载而归,但渔网也可能会损坏。 他们必须检查那些网。如果渔网有漏洞,他们将在下次出海前将其修复。 显然渔网的漏洞越小收获越多。所以捕鱼归来后,渔民们会将渔网的信息输入计算机,以检查渔网是否有漏洞。计算机检查渔网的原理很简单:每个渔网被视为一个由顶点和边构成的无向图。若图中的每个长度大于3的环都至少有一根弦(连接环上不相邻两点的边),计算机将输出“Perfect”,否则将输出“Imperfect”并尽力修复渔网。 # 输入格式 输入文件包括多组数据。 每组数据的第一行有两个整数$n,m$,分别代表顶点数和边数。其中$1\leq n \leq 1000$。 接下来$m$行描述渔网的边,每行包括两个整数$u,v$,代表$u$与$v$之间有一条连边。 输入文件以"0 0"结尾。 # 输出格式 对于每组数据输出“Perfect”或“Imperfect”, 每组数据的输出用换行符隔开。

题目描述

In a highly modernized fishing village, inhabitants there make a living on fishery. Their major tools, fishing nets, are produced and fixed by computer. After catching fishes each time, together with plenty of fishes, they will bring back the shabby fishing nets, which might be full of leaks. Then they have to inspect those nets. If there exist large leaks, they have to repair them before launching out again. Obviously, the smaller the leaks in the fishing nets are, the more fishes they will catch. So after coming back, those fishermen will input the information of the fishing nets into the computer to check whether the nets have leaks. The checking principle is very simple: The computer regards each fishing net as a simple graph constructed by nodes and edges. In the graph, if any circle whose length (the number of edges) is larger than 3 must has at least one chord, the computer will output "Perfect" indicating that the fishnet has no leaks. Otherwise, "Imperfect" will be displayed and the computer will try to repair the net. **Note:** A circle is a closed loop, which starts from one node, passes through other distinct nodes and back to the starting node. A chord is an edge, which connects two different nodes on the circle, but it does not belong to the set of edges on the circle.

输入输出格式

输入格式


The input file contains several test cases representing different fishing nets. The last test case in the input file is followed by a line containing 0 0. The first line of each test case contains two integers, _n_ and _m_ , indicating the number of nodes and edges on the net respectively, 1![$ \le$](http://acmicpc-live-archive.uva.es/nuevoportal/data/2424img1.png)_n_![$ \le$](http://acmicpc-live-archive.uva.es/nuevoportal/data/2424img1.png)1000 . It is followed by _m_ lines accounting for the details of the edges. Each line consists of two integers _x_ $ _{i} $ and _y_ $ _{i} $ , indicating there is an edge between node _x_ $ _{i} $ and node _y_ $ _{i} $ .

输出格式


For each test case, display its checking results. The word "Imperfect" suggests that the corresponding fishing net is leaking, while the word "Perfect" stands for a fishing net in good condition. Follow the output for each net with a blank line.

输入输出样例

输入样例 #1

4 4
1 2
2 3
3 4
4 1
3 3
1 2
2 3
3 1
0 0

输出样例 #1

Imperfect
Perfect