침략자 | cho.sh

미르코와 슬라브코는 리스크를 천 번도 넘게 해서, 같은 지도 모양 판에서 하는 새 게임 침략자를 만들고 있다. 판에는 1번부터 $N$ 번까지 번호가 붙은 나라 $N$ 개가 있고, 어느 나라끼리 이웃인지 정해져 있다. 국경을 맞대지 않은 두 나라도 이웃일 수 있다.

게임을 시작하기 전에 두 사람은 모든 나라에 탱크를 몇 대씩 배치하고, 일부 나라를 침략국으로 정한다. 나머지 나라는 평화국이다. 그다음 미르코와 슬라브코가 한 수씩 번갈아 둔다. 자기 차례에 둘 수 있는 수가 없는 사람이 진다. 미르코가 먼저 둔다.

차례가 오면 다음 두 가지 수 중 하나를 고른다.

공격:
- 탱크가 $T_A$ 대 있는 침략국 $A$ 와, $A$ 의 이웃이면서 탱크가 $T_P$ 대 있는 평화국 $P$ 를 고른다.
- 이 수는 $T_P > 0$ 일 때만 둘 수 있다.
- $A$ 에 있는 탱크가 각각 $P$ 의 탱크를 한 대씩 포탄으로 부순다.
- 수를 마치면 $P$ 에는 탱크가 $T_P - T_A$ 대 남고, $T_A > T_P$ 이면 0대가 된다.
지원:
- 서로 이웃인 평화국 $P$ 와 $Q$ 를 고른다. 탱크는 각각 $T_P$ 대, $T_Q$ 대 있다.
- 이 수는 $T_P > 0$ 일 때만 둘 수 있다.
- $T_P$ 가 홀수이면 먼저 $P$ 에 탱크를 한 대 추가한다.
- 그다음 $P$ 의 탱크 중 정확히 절반이 $Q$ 로 옮겨 간다.

나라는 어느 쪽의 소유도 아니다. 즉 차례가 온 사람은 규칙만 지킨다면 이웃한 두 나라를 마음대로 고를 수 있다.

판에 나라가 $N$ 개 있으므로 나라를 침략국과 평화국으로 나누는 방법은 $2^N$ 가지다. 두 사람은 각 방법마다 한 판씩 둔다. 둘 다 최적으로 둘 때 이 $2^N$ 판 중 미르코가 이기는 판이 몇 판이고 슬라브코가 이기는 판이 몇 판인지 구하라.

어떤 방법에서는 누구도 이길 수 없다. 예를 들어 침략국이 하나도 없으면 탱크를 부술 수 없어서 게임이 끝나지 않는다.

첫째 줄에 나라의 수 $N$ ( $2 \le N \le 40$ )이 주어진다.

둘째 줄에 게임을 시작할 때 각 나라에 있는 탱크 수가 1번 나라부터 $N$ 번 나라까지 차례대로 주어진다. 모두 40000보다 작은 자연수다.

셋째 줄에 이웃한 나라 쌍의 수 $M$ ( $1 \le M \le 780$ )이 주어진다.

다음 $M$ 개 줄에는 서로 이웃인 두 나라의 번호가 각각 주어진다. 같은 쌍이 두 번 이상 나오지는 않는다.

첫째 줄에 미르코가 이기는 판의 수를 출력한다.

둘째 줄에 슬라브코가 이기는 판의 수를 출력한다.

서로 이웃인 나라가 둘뿐이고 두 나라에 탱크가 100대씩 있다고 하자. 네 가지 방법 중 미르코가 두 판, 슬라브코가 한 판을 이긴다.

두 나라 모두 침략국이면 미르코가 둘 수 있는 수가 없으므로 슬라브코가 이긴다.
1번이 침략국이고 2번이 평화국이면 미르코가 한 수로 2번의 탱크를 모두 부순다. 그러면 슬라브코가 둘 수 있는 수가 없으므로 미르코가 이긴다.
1번이 평화국이고 2번이 침략국이면 같은 방법으로 미르코가 이긴다.
두 나라 모두 평화국이면 지원으로는 탱크 수가 줄지 않고 침략국도 없으므로, 두 사람이 어떻게 두든 지원하는 수가 항상 남아 있다. 이 방법에는 승자가 없다.