Alice, Bob, and Claire's Stone Game

Alice and Bob are playing a stone‐taking game with the help of Claire. There are n stones numbered from 1 to n. The game consists of 3 stages.

Stage 1: Alice and Bob take turns announcing which stone they intend to take. Alice goes first. On each turn, instead of saying exactly which stone they will take, the player announces two options – note that the two options may be identical, and a stone may even be announced again even if it was announced before. In this stage no stone is actually taken; the announcements only set an intention for Stage 3. Stage 1 ends after exactly n+1 announcements.

For example, for n=3, a possible Stage 1 (with 4 announcements) is:

1. Alice: "I will take either 1 or 3".
2. Bob: "I will take 2 or 2".
3. Alice: "I will take 3 or 2".
4. Bob: "I will take either 1 or 3".

Stage 2: For each of the n+1 announcements, Claire selects one of the two options – she says "first" or "second" for each announcement. We call the resulting sequence of choices a scheme. In total, there are \(2^{n+1}\) possible schemes (even if in some announcement the two options are the same, we consider choosing first and second as different choices).

For example, one of the 16 schemes when n=3 is:

1. "first": so Alice will take stone 1.
2. "first": so Bob will take stone 2.
3. "second": so Alice will take stone 2.
4. "first": so Bob will take stone 1.

Stage 3: The players take turns actually taking the stones according to the order of announcements and Claire’s choices. The stone picked in each move is the one corresponding to Claire’s choice for that move. The first player who is unable to take the stone they intended (because it was already taken) loses, and the other wins. (Note that since there are n stones but n+1 moves, one player is guaranteed to eventually lose.)

In the example above, Alice takes stone 1, Bob then takes stone 2, and then Alice finds that stone 2 has already been taken – so Alice loses and Bob wins.

---

At some point during Stage 1, a sequence of k announcements has already been made. (These announcements might be completely arbitrary.) From this point onward, both players will play optimally, meaning that regardless of how the game is played, Claire’s choice will be uniformly random among all \(2^{n+1}\) schemes, and each player will choose their future announcements so as to minimize the number of schemes in which they lose.

Your task is: given the integer n and the current sequence of k announcements in Stage 1, compute the number of schemes (over Claire’s random choices) under which Alice wins, and the number under which Bob wins, assuming both play optimally from now on.

Optimal play insight: When a player has the option, they will announce a pair (x, x) with a stone x that is fresh – it has not appeared in any previous announcement (from Stage 1) – so that regardless of Claire’s choice the move is safe. Since there are only n stones and n+1 moves, one move must eventually be forced to be a duplicate. The outcome of the game is decided by the first move (in order) that results in a duplicate. For announcements already made (the prefix) the coin‐flip by Claire makes the outcome probabilistic, while for future moves both players can secure their safe moves if a fresh stone is available. Let P be the set of stones that appear in the k prefix announcements, and let \(R = n - |P|\) be the number of stones not mentioned in the prefix. Then if the prefix yields no duplicate, the forced duplicate will occur at move \(k + R + 1\), and the loser is determined by whose turn that move is.

Note that even though there are \(2^{n+1}\) total schemes, the optimal strategy in the remaining moves makes the outcome depend solely on the prefix outcomes and a forced duplicate later.

inputFormat

The first line contains two integers n and k (1 ≤ n, k ≤ 10⁵, with k ≤ n+1).

Then follow k lines, each containing two integers a_i and b_i (1 ≤ a_i, b_i ≤ n) representing the two options announced in the i-th move in Stage 1.

If k is 0, then no announcement has been made yet.

outputFormat

Output two integers: the number of schemes in which Alice wins and the number in which Bob wins.

sample

3 4
1 3
2 2
3 2
1 3

4 6