All Tracks Algorithms Dynamic Programming Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?