축제

바이트버그에서 자선 축제가 열리고 있고, 당신은 모금 담당자 중 한 명입니다. 당신은 장애물 달리기 경주를 비롯한 여러 행사를 놓쳤습니다. 퍼즐 애호가인 바이트아사르는 자신이 낸 수수께끼를 풀면 큰 금액을 기부하겠다고 약속합니다.

당신은 경주 결과를 알지 못하지만, 바이트아사르가 일부 정보를 알려 주며 이렇게 묻습니다. 그가 알려 준 모든 조건에 어긋나지 않으면서 선수들이 기록할 수 있는 서로 다른 완주 시간의 최대 개수는 얼마일까요? 같은 순간에 결승선을 통과한 선수들은 같은 시간을 가집니다.

모든 선수의 완주 시간은 정수 초입니다. 바이트아사르는 선수들의 시간 사이에 성립하는 두 종류의 관계를 알려 줍니다.

• 어떤 쌍 $(a, b)$: 선수 $a$의 시간이 선수 $b$의 시간보다 정확히 $1$초 작았다.
• 어떤 쌍 $(c, d)$: 선수 $c$의 시간이 선수 $d$의 시간보다 크지 않았다.

선수들이 기록할 수 있는 서로 다른 시간의 최대 개수를 구하는 프로그램을 작성하세요.

첫째 줄에 세 정수 $n$, $m_1$, $m_2$가 주어집니다 ($2 \le n \le 600$, $1 \le m_1 + m_2 \le 100\,000$). 각각 선수의 수, 첫 번째 종류의 관계 수, 두 번째 종류의 관계 수를 뜻합니다. 선수는 $1$번부터 $n$번까지 번호가 매겨집니다.

다음 $m_1$개의 줄에는 각각 두 정수 $a_i$와 $b_i$가 주어집니다 ($a_i \ne b_i$). 선수 $a_i$의 시간이 선수 $b_i$의 시간보다 정확히 $1$초 작았음을 뜻합니다.

그다음 $m_2$개의 줄에는 각각 두 정수 $c_i$와 $d_i$가 주어집니다 ($c_i \ne d_i$). 선수 $c_i$의 시간이 선수 $d_i$의 시간보다 크지 않았음을 뜻합니다.

바이트아사르가 알려 준 모든 관계와 어긋나지 않는, 서로 다른 완주 시간의 최대 개수를 정수 하나로 출력합니다.

모든 관계를 만족하는 시간 배정이 존재하지 않으면, 대신 NIE라는 단어 하나만 출력합니다.

첫 번째 예제에서는 조건에 맞는 결과가 두 가지 있습니다.

1. 선수 $3$이 $1$위, 선수 $1$과 $4$가 공동 $2$위, 선수 $2$가 마지막.
2. 선수 $1$과 $3$이 공동 $1$위, 선수 $2$와 $4$가 공동 $2$위.

첫 번째 결과는 서로 다른 시간이 세 가지로 두 번째보다 많으므로, 정답은 $3$입니다.