Red Sticker Coverage

There are \(n\) cups of alcohol labeled \(1\sim n\) on a table, and plenty of red papers with the Chinese character "酒". You will perform \(m\) operations sequentially on these cups. The operations are of two types:

• 1 x: Attach one red paper to cup \(x\).
• 2 x: Attach one red paper to every cup except cup \(x\).

Your task is to determine the minimum number of operations (taken in order from the beginning) required so that every cup has at least one red paper on it. If it is impossible to achieve this even after all \(m\) operations, output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\)). Each of the following \(m\) lines contains an operation in one of the following forms:

• 1 x
• 2 x

Here, \(x\) is an integer satisfying \(1 \le x \le n\).

outputFormat

Output a single integer, the minimum number of operations required so that every cup has at least one red paper. If it is impossible, output -1.

sample

3 5
1 1
2 2
1 3
2 1
1 2

2