P9126 [USACO23FEB] Moo Route II S

**Note: The time limit for this problem is 4s, twice the default.** Bessie is on vacation! Due to some recent technological advances, Bessie will travel via technologically sophisticated flights, which can even time travel. Furthermore, there are no issues if two "parallel" versions of Bessie ever meet. In the country there are $N$ airports numbered $1,2,\cdots ,N$ and $M$ time-traveling flights $(1 \le N,M \le 200000)$. Flight $j$ leaves airport $c_j$ at time $r_j$, and arrives in airport $d_j$ at time $s_j (0 \le rj,sj \le 10^9$, $s_j

N/A

N/A

### Explanation for Sample 1 Bessie can take the $3$ flights in the listed order, which allows her to arrive at airports $1$ and $2$ at time $0$, and airport $3$ at time $20$. Note that this route passes through airport $2$ twice, first from time $10-11$ and then from time $0-1$. ### Explanation for Sample 2 In this case, Bessie can take flight $1$, arriving at airport $2$ at time $10$. However, she does not arrive in time to also take flight $2$, since the departure time is $10$ and she cannot make a $1$ time-unit layover. ### SCORING - Inputs $3-5$: $r_j