문제
언어학자 동훈이는 새로운 언어를 만들었는데, 그 언어는 무려 n개의 철자가 있다. 지금 여기서 n개를 다 배울 수는 없기 때문에 우리는 첫번째 철자를 1로 시작해서 각각 2,3,…,n이라고 하자.
어떤 철자는 다른 철자로 바뀔수가 있다. 이것을 xy로의 “변화”라고 부르기로 하자. 변화는 다음과 같은 법칙을 따른다.
x가 y로 변화할 수 있으면, y도 x로 변화할 수 있다. // if xy , then yx
x 가 y로 변화할 수 있고, y가 z로 변화할 수 있으면 x도 z로 변화할 수 있다. //if xy and yz then xz
당신에게 수열 S를 줄 것이다. S는 m개의 철자(1부터 n사이의 어떤 정수)로 되어있다. 또한 당신에게 k개의 가능한 변화 규칙을 줄 것이다. 이 변화를 쓰든 안 쓰든, 또는 여러 번 쓰든 그것은 여러분의 자유이다.
S에 속해있는 철자들을 변화시키거나 빼서 회문을 만들 때, 가장 긴 회문의 길이를 출력하라. 회문(Palindrome)이란, 앞으로 읽든 뒤로 읽든 같은 문장을 말한다.
예를 들어, 1 4 5 9 3 1의 수열이 있고, 변화 43이 가능하다고 하자.
변화를 통해 수열은 1 3 5 9 3 1 이 되고, 9를 삭제함으로써, 수열은 1 3 5 3 1이 된다. 이것이 가장 긴 길이 5의 회문이며, 길이 5의 다른 회문을 만들 수는 있지만, 이것보다 긴 길이의 회문은 없다.
입력
첫 줄에 3개의 정수 n, k, m이 주어진다. ( 1≤n≤105, 1≤k≤106, 1≤m≤103) n은 철자의 개수, k는 가능한 변화의 개수, m은 수열S에 들어가는 철자의 개수이다.
다음 k줄에 걸쳐 x와 y가 주어지며, 이는 xy의 변화가 가능하다는 뜻이다.
마지막 줄에 S가 m개의 정수 수열로 주어진다. 이 정수들은 한 줄에 걸쳐 공백을 사이에 두고 주어진다. (당연히 정수 수열의 구성원과 x,y는 모두 1이상 n이하이다.)
출력
변화와 삭제 작업으로 만들 수 있는 가장 긴 회문의 길이를 출력하라.
예제 #1
10 8 15
1 2
1 3
2 7
3 1
4 5
6 8
9 6
10 5
1 4 5 7 9 8 1 3 10 4 5 10 2 7 8
10
예제 #2
10 7 6
1 3
5 7
3 5
2 6
2 4
8 4
10 9
1 9 2 3 10 3
5
로그인해야 코드를 작성할 수 있어요.