이중마법 완전정복

기혜력 2119년 15월. 궁정 마술사 Sengemon Lugene의 손에 의해 한 권의 마법서가 쓰였다. 이 마법서 "In Magiray"는 이 세계 마법 법칙의 근간에 깊이 관여하는 "이중마법"을 누구나 습득할 수 있는 기술로 체계화했다는 점에서 혁신적인 책이었다. 우선 이 책의 내용을 요약한 것을 살펴보자.

【엘리먼트】

세계의 모든 물체는 "샘", "바람", "깃", "꽃", "모래", "등불"…… 같은 극소 요소 "엘리먼트"로 구성되어 있다. 엘리먼트에는 많은 종류가 있고, 인간은 엘리먼트와 계약을 맺음으로써 계약한 종류의 엘리먼트를 사용한 이중마법을 발동시킬 수 있다.

【이중마법】

이중마법이란 이름 그대로 두 엘리먼트를 겹쳐서 풀어놓는 마법이다. 주가 되는 엘리먼트를 "주속성", 다른 쪽을 "부속성"이라 부른다. 예를 들어 주속성이 "등불"이고 부속성이 "꽃"이면 그 이중마법은 (등불, 꽃)으로 표기한다. (등불, 꽃)과 (꽃, 등불)은 다른 이중마법이다. 또 주속성과 부속성은 같아도 된다.

【키워드】

"샘→ huda", "바람→ loar", "깃→ sheza", "꽃→ leide"처럼 각각의 엘리먼트에 각각 짧은 "키워드"를 일대일 대응시킬 수 있다. 키워드는 엘리먼트가 가진 성질을 짧은 말로 상징하게 함으로써, 몇 개의 연속된 키워드열을 외우기만 하면 간단히 이중마법을 발동시키는 것을 가능하게 한 획기적인 개념이다.

【주문】

"huda, leide, loar, sheza"처럼 하나 이상의 키워드를 연속해서 나열한 것을 "주문"이라 한다. 술자가 의도한 주문을 외움으로써 대응하는 이중마법을 발동시킬 수 있다. 구체적으로는 주문의 가장 첫 키워드에 대응하는 엘리먼트를 주속성, 가장 마지막 키워드에 대응하는 엘리먼트를 부속성으로 하는 이중마법이 발동한다. 앞의 주문 예라면 발동하는 이중마법은 (샘, 깃)이다. 주문이 키워드 하나만으로 이루어진 경우에는 주속성도 부속성도 그 키워드에 대응하는 엘리먼트가 된다.

【엘리먼트 간의 궁합】

"huda, leide, loar, sheza" 주문으로 (샘, 깃)의 이중마법이 발동한다는 것은 이미 말했다. 그러나 언뜻 보면 (샘, 깃)을 쓰고 싶다면 굳이 긴 주문을 외우지 않고 "huda, sheza"만으로도 될 것처럼 보인다. 하지만 실제로는 불가능하다. "샘(huda)"과 "깃(sheza)"은 궁합이 좋지 않아 이 둘이 이웃한 주문을 외우면 반발 작용이 일어나 엘리먼트끼리 상쇄되기 때문이다. 한편 "샘(huda)"과 "꽃(leide)", "꽃(leide)"과 "바람(loar)", "바람(loar)"과 "깃(sheza)"는 어느 짝이든 궁합이 좋으므로 "huda, leide, loar, sheza"나 "loar, leide, huda" 같은 주문에서는 엘리먼트의 상쇄가 일어나지 않는다.

【주문 논리】

이중마법을 쓰려는 사람은 미리 모든 궁합이 좋은 엘리먼트 짝 각각에 대해 어느 키워드가 "상위 워드"이고 어느 키워드가 "하위 워드"인지 정의해 두어야 한다. 궁합이 좋은 두 엘리먼트의 키워드 "A"와 "B"에 대해 A를 상위 워드, B를 하위 워드로 정의했을 때 A > B로 표기한다. A > B일 때 하나의 주문 안에서 B 바로 뒤에 A를 나열할 수 없다. 즉 "A1, A2, A3, ……, Ak"가 올바른 주문이라면 A1 > A2, A2 > A3, ……, A**k-1 > Ak여야 한다. 참고로 A > B이고 B > C여도 A > C일 필요는 없다.

이렇게 각 술자가 상위, 하위 워드를 자기 마음대로 정의하는 것을 "주문 논리 구축"이라 부른다. 이는 일부러 주문의 구문에 제약을 두어 엘리먼트의 흐름을 명확히 하고 목적하는 이중마법의 성공 확률을 높이기 위한 궁리이다. 그러나 그 대가로 주문 논리를 구축하면 어떻게 주문을 외워도 발동시킬 수 없는 이중마법이 생길 수 있다(단, 어떤 주문 논리를 구축해도 쓸 수 없는 이중마법은 존재하지 않는다는 것이 증명되어 있다). 이런 사정이 있어 어떤 주문 논리를 구축할지는 예나 지금이나 많은 마술사를 괴롭히는 까다로운 문제이다.

어느 작은 마을에 사는 견습 마술사 소년 유토는 모든 엘리먼트와의 계약을 마치고 내일 자신의 주문 논리를 구축하기 위한 의식을 치르려 한다. 유토는 단순히 가능한 한 많은 종류의 이중마법을 발동시킬 수 있는 주문 논리가 좋은 주문 논리라고 생각했다.

초일급 전술기사(현대 일본으로 치면 슈퍼 프로그래머)인 당신은 친구 유토로부터 주문 논리를 잘 구축하면 최대 몇 종류의 이중마법을 쓸 수 있게 되는지 알고 싶다는 상담을 받았다. 이는 지금까지 전 세계 사람들이 도전해 왔지만 아무도 풀 수 없었던 난제이다. 만약 풀 수 있다면 당신의 이름은 미래영겁 전 세계에서 이야기될 것이다.

N M
s1
s2
.
.
.
sN
p1 q1 p2 q2 .
.
.
pM M

입력의 첫 줄에는 정수 N과 정수 M이 공백으로 구분되어 쓰여 있다. 이는 엘리먼트가 모두 N종류, 궁합이 좋은 엘리먼트 짝이 모두 M쌍 존재함을 나타낸다.

이어지는 N줄에는 문자열 하나가 쓰여 있다. 1 + i번째 줄에 쓰인 문자열 si는 i번째 엘리먼트에 대응하는 키워드가 si임을 나타낸다.

이어지는 M줄에는 두 문자열이 공백으로 구분되어 쓰여 있다. 1 + N + i번째 줄에 쓰인 문자열 pi와 qi는 키워드 pi에 대응하는 엘리먼트와 키워드 qi에 대응하는 엘리먼트의 짝이 궁합이 좋음을 나타낸다. 반대로 여기에 나타나지 않은 엘리먼트 짝은 궁합이 좋지 않다.

이 데이터는 다음 조건을 만족한다.

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 4,950
• si는 알파벳 대문자 또는 소문자로만 이루어진, 1자 이상 15자 이하의 문자열이다.
• i ≠ j ⇒ si ≠ sj
• pi ≤ qi
• i ≤ j ⇒ (pi, qi) ≠ (pj, qj)이고 (pi, qi) ≠ (qj, pj)
• 어떤 주문 논리를 구축해도 발동할 수 없는 이중마법은 존재하지 않는다.

주문 논리를 구축했을 때 사용할 수 있게 되는 이중마법 종류의 최댓값을 출력하라.