Flight
View as PDFThe kingdom of Pekoland has ~n~ cities numbered from ~1~ to ~n~. A day in Pekoland is divided into ~10^9~ time units, where time ~0~ is midnight. The people of Pekoland mainly travel between cities by plane. Every day, there are ~m~ flights in Pekoland, where the ~i~-th flight departs from city ~u_i~ at time ~x_i~ and lands in city ~v_i~ at time ~y_i~. Thanks to modern infrastructure, the check-in process at airports takes negligible time, so a passenger arriving in city ~u~ at time ~t~ can choose to take any flight departing from ~u~ from time ~t~ onwards.
There are two airlines operating in Pekoland, and all flights here are operated by either of them. Pekoland Airlines is the royal airline, and all flights of Pekoland Airlines are guaranteed to fly on schedule. In contrast, PekoJet Air is a newly established low-cost airline, and its flights may be canceled without notice. Nevertheless, PekoJet Air commits to having at most ~k~ flights canceled each day.
Aqua is a foreign tourist. She has just landed in city ~1~—the capital of Pekoland—at midnight (time ~0~). Aqua wants to fly to city ~n~, which is preparing to celebrate the ~50~-th anniversary of the unification of the kingdom. Assuming Aqua is in city ~u~ at time ~t~, she can choose to check in for one of the flights departing from ~u~ at time ~t~, or choose to do nothing (wait until time ~t+1~). If there are multiple flights departing at the same time, Aqua can only choose one flight to check in for, and she can only know whether that flight is canceled or not after she has checked in. If the flight is canceled, she will remain in city ~u~ at time ~t+1~; otherwise, she will land in the destination city according to the flight schedule.
To find the best spot for the parade the next morning, Aqua wants to reach city ~n~ within the day and as early as possible. Specifically, Aqua wants to know the smallest time ~x~ such that she can arrive at ~n~ before or at time ~x~, regardless of which flights are canceled. If Aqua cannot be sure to reach ~n~ within the day, print ~-1~. Please help Aqua!
Input
Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10\,000~). The description of each test case is as follows.
The first line contains three integers ~n~, ~m~, ~k~ (~2 \leq n \leq 10^5~, ~1 \leq m \leq 2 \cdot 10^5~, ~0 \leq k \leq m~) — the number of cities in Pekoland, the number of daily flights in Pekoland, and the maximum number of flights of PekoJet Air that can be canceled in a day.
The ~i~-th of the next ~m~ lines contains five integers ~u_i~, ~v_i~, ~x_i~, ~y_i~, ~p_i~ (~1 \leq u_i, v_i \leq n~, ~u_i \neq v_i~, ~0 \leq x_i < y_i < 10^9~, ~1 \leq p_i \leq 2~) describing a flight. The ~i~-th flight departs from city ~u_i~ at time ~x_i~ and lands in city ~v_i~ at time ~y_i~. The ~i~-th flight is operated by Pekoland Airlines if ~p_i = 1~ and by PekoJet Air if ~p_i = 2~.
It is guaranteed that:
the sum of ~n~ across all test cases does not exceed ~10^5~,
the sum of ~m~ across all test cases does not exceed ~2 \cdot 10^5~.
Output
For each test case, print the smallest time ~x~ such that Aqua can arrive at ~n~ before or at time ~x~, regardless of how many flights are canceled. If she cannot be sure to reach ~n~ within the day, print ~-1~.
Scoring
| Subtask | Points | Constraints |
|---|---|---|
| 1 | ~500~ | ~p_i = 1~ for all ~1 \leq i \leq m~ |
| 2 | ~1000~ | ~\sum n \le 1\,000~, ~\sum m \le 1\,000~ |
| 3 | ~1750~ | No additional constraints |
| Total | ~3250~ |
Sample Input 1
3
2 4 1
1 2 0 12 1
1 2 2 10 2
1 2 3 7 2
1 2 3 4 2
5 6 1
1 2 1 5 1
1 3 1 5 1
1 4 1 5 1
2 5 5 10 2
3 5 5 10 2
4 5 5 10 2
4 7 2
1 2 0 2 2
1 3 1 3 1
2 3 2 3 2
2 4 4 6 1
3 2 3 4 2
3 4 4 7 2
3 4 5 7 2
Sample Output 1
10
-1
7
Notes
In the first example, Aqua can arrive at city ~2~ at the latest by time ~10~ with the following plan:
Skip flight ~1~, check in for flight ~2~ at time ~2~.
If flight ~2~ is not canceled, Aqua lands in city ~2~ at time ~10~.
Otherwise, Aqua checks in for flight ~4~. This flight is guaranteed not to be canceled since flight ~2~ has been canceled, so Aqua lands in city ~2~ at time ~4~.
Note that if Aqua does not check in for flight ~2~, she cannot ensure reaching city ~2~, as flights ~3~ and ~4~ depart at the same time and she can only choose to check in for one of these two flights (and the flight she chooses can always be canceled).
Here is an illustration for the first example:
The blue edge represents flights from ~\color{blue}{Pekoland\,Airlines}~.
The red edge represents flights from ~\color{red}{PekoJetAir}~.
The green number on the edge is the departure time of flight ~\color{green}{x_i}~.
The orange number on the edge is the landing time of flight ~\color{orange}{y_i}~.
Illustration for the first example
In the second example, Aqua can choose to fly to city ~2~, ~3~, or ~4~ at time ~5~. However, regardless of which city she chooses, the only flight connecting that city to city ~5~ could be canceled. Therefore, the answer is ~-1~.
Illustration for the second example
In the third example, PekoJetAir guarantees that no more than 2 flights will be canceled. Aqua can reach city ~4~ at the latest by time ~7~.
At city ~1~, at time ~0~, Aqua can check in for a flight from PekoJet Air.
If the flight is not canceled, Aqua can continue to city ~4~ on a flight from Pekoland Airlines at time ~6~. Aqua has reached her destination.
If the flight is canceled, Aqua arrives in city ~3~ at time ~3~ on a flight from Pekoland Airlines.
When at city ~3~ at time ~3~, Aqua can try a flight from PekoJet Air to city ~2~.
If the flight is not canceled, Aqua can continue to city ~4~ on a flight from Pekoland Airlines at time ~6~. Aqua has reached her destination.
If the flight is canceled, Aqua stays in city ~3~ and considers the flight to city ~4~.
By this time, PekoJet Air has canceled 2 flights, so the airline cannot cancel any more flights.
Aqua can take any flight from PekoJet Air to city ~4~ at time ~7~. Aqua has reached her destination.
Illustration for the third example
Comments
ahjhj tao bi g.a.y va ng0k nhe
uk toi bi ng0k nhe ahjhj
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.