Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
75 - ZOJ Monthly, February 2009 - C
Couples

Time Limit: 1 Second      Memory Limit: 32768 KB

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.
1. If two persons with "8g" relationship stands next to each other, they may run away and never come back.
2. If the people between the ith person and the jth person all ran away, now the ith one and the jth one are considered to be next to each other.

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
Submit    Status