Double Move

Alice와 Bob이 게임을 하고 있고, Claire가 이들을 돕는다. 돌은 $1$부터 $n$까지 번호가 매겨져 있다. 게임은 세 단계로 진행된다.

첫 번째 단계에서는 Alice와 Bob이 번갈아 수를 둔다. Alice가 먼저 둔다. 각 차례에 플레이어는 돌을 하나 가져가겠다는 의사를 밝히는데, 어느 돌인지 말하지 않고 두 가지 후보를 제시한다. 두 후보가 같아도 된다. 앞선 차례에서 이미 언급된 돌을 다시 언급해도 된다. 이 단계에서는 실제로 돌을 가져가지 않는다. 선언이 $n+1$번 이루어지면 첫 번째 단계가 끝난다.

두 번째 단계에서는 선언된 $n+1$개 각각에 대해 Claire가 두 후보 중 하나를 "first" 또는 "second"로 고른다. Claire가 고른 $n+1$개의 선택 순서 하나를 시나리오라고 한다. 시나리오는 정확히 $2^{n+1}$가지다. 한 선언의 두 후보가 같더라도 "first"와 "second"는 서로 다른 시나리오로 센다.

세 번째 단계에서는 Alice와 Bob이 Claire의 선택에 따라 실제로 돌을 가져간다. 필요한 돌이 이미 가져가져 수를 둘 수 없는 플레이어가 처음으로 진다. 돌은 $n$개이고 차례는 $n+1$번이므로 반드시 누군가는 진다.

Alice와 Bob은 Claire가 $2^{n+1}$개의 시나리오를 같은 확률로 고른다는 것을 안다. 최적으로 플레이할 때 각 플레이어는 자신이 지는 시나리오 수를 최소화하려 한다.

$n$과 첫 번째 단계 도중의 상태가 주어진다. 이미 이루어진 선언은 $k$개이며, 임의의 내용일 수 있다. 이 시점부터 Alice와 Bob이 위와 같이 최적으로 플레이한다. 각 플레이어에 대해 그 플레이어가 이기는 시나리오 수를 구하라.

첫 줄에 공백으로 구분된 두 정수 $n$과 $k$ ($1 \le n \le 35$, $0 \le k \le n+1$)가 주어진다. 돌의 개수와 이미 이루어진 선언의 개수다.

이어지는 $k$개의 줄에는 선언된 순서대로 각 선언의 두 돌 번호가 공백으로 구분되어 주어진다. 두 번호 모두 $1$ 이상 $n$ 이하이며, 서로 같을 수 있다.

$k < n+1$이면 다음 선언을 누가 하는지는 $k$의 홀짝으로 정해진다.

한 줄에 공백으로 구분된 두 정수를 출력한다. 첫 번째 수는 Alice가 이기는 시나리오 수이고, 두 번째 수는 Bob이 이기는 시나리오 수다. 두 플레이어가 남은 게임을 최적으로 둔다고 가정한다. 두 수의 합은 $2^{n+1}$이어야 한다.

첫 번째 예제는 문제 설명의 예시에 해당한다. 남은 선언이 없으므로 Claire의 선택 중 Alice가 이기는 경우와 Bob이 이기는 경우를 세면 된다. Claire가 첫 수로 돌 $1$, 두 번째 수로 돌 $3$을 고르면 Alice가 이기고, 그 밖의 경우에는 Alice가 진다.

두 번째 예제에서 Alice가 처음에 "1 1"을 선언하면 Bob은 "2 2"로 답한다. 이후 Alice가 세 번째에 무엇을 선언하든 진다. Claire가 첫 수로 돌 $1$, 두 번째 수로 돌 $2$를 고르면 세 번째 수에서 Alice가 가져갈 돌이 남지 않기 때문이다. 이것은 Alice의 최선의 첫 수가 아니다. 대신 "1 2"를 선언해야 한다. 그러면 그 뒤에 Bob과 Alice가 어떻게 두든 각자 $8$가지 중 $4$가지에서 이긴다.