
ZOJ Problem Set  3160
In the world of knowledge, so many new words appear on the internet. A special one is "8g", a kind of special relationship between two persons. (If you want to know more words, just turn to a search engine.) You are given n people and the "8g" relationships between them. Now they are standing in one line and the following things may happen. According to the rules, when a person has "8g" relationships with the two persons in his/her two sides. He/She can run with either one. So there may be many ways in which people could run. So, for all possibility, we want to know the maximum number of persons that can run in total. Input The first line of each case will contain two integers n(2 <= n <= 300) and m, indicating the number of persons and the number of "8g" relationships(Persons are indexed from 0 to n  1). Next m lines contains two integers a and b, meaning that there is a "8g" relationship between a and b. Then followed by a line containing a permutation of 0 to n  1, meaning the arrangement of the n persons. Proccess to the end of file. Output For each case, print one line containing the maximum number of people that can run in total. Sample Input 4 2 0 3 1 2 0 1 2 3 Sample Output 4 Author: ZHUANG, Junyuan Source: ZOJ Monthly, February 2009 