Game
Tag(s):

## Algorithms, Dynamic Programming, Easy

Problem
Editorial
Analytics

Consider the following game. There is a field with $n$ rows and $3$ columns. Some cells contain obstacles. But the first row is always empty. Let's define cell in $i$-th row and $j$-th column as $(i, j)$. From cell $(i, j)$ you can go to cells $(i + 1, j - 1)$, $(i + 1, j)$ and $(i + 1, j + 1)$ if such cell exists (you can't go out of field) and doesn't contain obstacle. You can start in any column in the first row. What is the maximum $i$, such that $i$-th row is reachable?

Input format

Given several test cases.

First line of input contains integer $T$ ($1 \leq T \leq 3 \cdot 10^5$) — number of test cases.

Then follow $T$ blocks of input.

The first line of block contains integers $n$ and $q$ ($2 \leq n \leq 10^9$, $0 \leq q \leq \min(3 \cdot 10^5, 3 \cdot (n - 1))$) — number of rows and number of obstacles, respectively.

Then follow $q$ lines with obstacles description.

The $i$-th of them contains integers $x$ and $y$ ($2 \leq x \leq n$, $1 \leq y \leq 3$) — the coordinates of $i$-th obstacle, located at $(x, y)$.

Coordinates of all obstacles in a single test case are pairwise distinct.

Sum of all $q$ in input doesn't exceed $3 \cdot 10^5$.

Output format

For each block print single integer — the maximum row that is possible to be reached.

SAMPLE INPUT
2
4 3
2 2
2 3
4 1
2 3
2 1
2 2
2 3

SAMPLE OUTPUT
4
1

Explanation

In the first test case one of the optimal paths is $(1, 2)$, $(2, 1)$, $(3, 2)$, $(4, 2)$. So the row $4$ is possible to be reached.

In the second test case there are no possible moves from $(1, 2)$. So only the row $1$ is possible to be reached.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Math > Number Theory
• Algorithms > Graphs
• Algorithms > Graphs
• Data Structures > Advanced Data Structures