Contiguous Soldiers Preparation Swap

There are n soldiers numbered from \(1\) to \(n\) from left to right, each in one of two states: prepared or unprepared. You are given \(m\) commands. The \(i\)th command instructs the soldiers at positions \(a_i\) and \(b_i\) to swap places, but the swap only occurs if the soldier at \(a_i\) is prepared and the soldier at \(b_i\) is unprepared. Otherwise, the command is ignored.

For every integer \(k\) satisfying \(1 \le k \le n\), consider all \(\binom{n}{k}\) possible initial configurations with exactly \(k\) prepared soldiers. After executing the \(m\) commands, determine how many initial configurations yield a final arrangement in which the prepared soldiers form a contiguous segment. Output the answer modulo \(2\).

Note: A configuration is represented by a binary string of length \(n\) (with \(1\) indicating a prepared soldier and \(0\) an unprepared one). A contiguous segment means that if the first occurrence of \(1\) is at index \(L\) and the last at index \(R\), then every index \(i\) with \(L \le i \le R\) must be \(1\), and all indices outside this range must be \(0\). The commands are executed sequentially; for each command, if the soldier at position \(a_i\) is prepared and the soldier at position \(b_i\) is unprepared, then they swap positions (i.e. their states are exchanged).

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of soldiers and the number of commands.

Each of the following \(m\) lines contains two integers \(a_i\) and \(b_i\) (\(1 \le a_i, b_i \le n\)), representing a command.

outputFormat

Output a single integer: the parity (i.e. modulo \(2\)) of the number of initial configurations (with at least one prepared soldier) that, after executing all commands, result in all prepared soldiers forming a contiguous segment.

sample

2 1
1 2

1