Bay
Xem dạng PDFVương quốc Pekoland có ~n~ thành phố được đánh số từ ~1~ đến ~n~. Một ngày ở Pekoland được chia thành ~10^9~ đơn vị thời gian, trong đó thời điểm ~0~ là nửa đêm. Người dân Pekoland chủ yếu di chuyển giữa các thành phố bằng máy bay. Hàng ngày, có ~m~ chuyến bay ở Pekoland, trong đó chuyến bay thứ ~i~ khởi hành tại thành phố ~u_i~ vào thời điểm ~x_i~ và hạ cánh tại thành phố ~v_i~ vào thời điểm ~y_i~. Nhờ hạ tầng tối tân, việc làm thủ tục tại các sân bay mất thời gian không đáng kể, do vậy một hành khách tới thành phố ~u~ vào thời điểm ~t~ có thể chọn bay tiếp bất kỳ chuyến bay nào xuất phát tại ~u~ từ thời điểm ~t~ trở đi.
Có hai hãng hàng không hoạt động ở Pekoland, và mọi chuyến bay ở đây đều được khai thác bởi một trong hai hãng này. Pekoland Airlines là hãng hàng không hoàng gia, mọi chuyến bay của Pekoland Airlines đều đảm bảo bay đúng kế hoạch. Ngược lại, PekoJet Air là một hãng hàng không giá rẻ mới thành lập, những chuyến bay của hãng này có thể bị hủy mà không báo trước. Dù vậy, PekoJet Air cam kết mỗi ngày chỉ có tối đa ~k~ chuyến bay bị hủy.
Aqua là một du khách nước ngoài. Cô vừa đáp xuống thành phố ~1~—kinh đô của Pekoland—vào nửa đêm (thời điểm ~0~). Aqua muốn bay tới thành phố ~n~, nơi chuẩn bị kỷ niệm ~50~ năm ngày thống nhất vương quốc vào ngày mai. Giả sử Aqua đang ở thành phố ~u~ vào thời điểm ~t~, cô có thể chọn làm thủ tục cho một trong các chuyến bay khởi hành từ ~u~ vào thời điểm ~t~, hoặc chọn không làm gì (đợi đến thời điểm ~t+1~). Nếu có nhiều chuyến bay cùng khởi hành một lúc, Aqua chỉ có thể chọn một chuyến bay để làm thủ tục, và cô chỉ có thể biết chuyến bay đó có bị hủy hay không sau khi đã làm thủ tục xong. Nếu chuyến bay bị hủy, cô sẽ ở lại thành phố ~u~ ở thời điểm ~t+1~, ngược lại cô sẽ hạ cánh ở thành phố đích theo đúng lịch trình của chuyến bay.
Để tìm được vị trí ưng ý nhất trong buổi diễu hành vào sáng ngày hôm sau, Aqua muốn đến thành phố ~n~ trong ngày và sớm nhất có thể. Cụ thể, Aqua muốn biết thời điểm ~x~ nhỏ nhất sao cho cô có thể đến ~n~ vào trước hoặc đúng thời điểm ~x~, bất kể những chuyến bay nào bị hủy. Nếu Aqua không thể chắc chắn đến ~n~ trong ngày, in ra ~-1~. Hãy giúp Aqua nhé!
Input
Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 10\,000~). Mô tả của mỗi test case như sau.
Dòng đầu tiên chứa ba số nguyên ~n~, ~m~, ~k~ (~2 \leq n \leq 10^5~, ~1 \leq m \leq 2 \cdot 10^5~, ~0 \leq k \leq m~) — số thành phố ở Pekoland, số chuyến bay hàng ngày ở Pekoland, và số chuyến bay tối đa của PekoJet Air có thể bị hủy trong ngày.
Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa năm số nguyên ~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~) mô tả một chuyến bay. Chuyến bay thứ ~i~ khởi hành tại thành phố ~u_i~ vào thời điểm ~x_i~ và hạ cánh tại thành phố ~v_i~ vào thời điểm ~y_i~. Chuyến bay thứ ~i~ được khai thác bởi Pekoland Airlines nếu ~p_i = 1~ và PekoJet Air nếu ~p_i = 2~.
Đảm bảo rằng:
tổng của ~n~ qua tất cả các test case không vượt quá ~10^5~,
tổng của ~m~ qua tất cả các test case không vượt quá ~2 \cdot 10^5~.
Output
Với mỗi test case, in ra thời điểm ~x~ nhỏ nhất sao cho cô có thể đến ~n~ vào trước hoặc đúng thời điểm ~x~, bất kể những chuyến bay bị hủy ra sao. Nếu Aqua không thể chắc chắn đến ~n~ trong ngày, in ra ~-1~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~500~ | ~p_i = 1~ với mọi ~1 \leq i \leq m~ |
| 2 | ~1000~ | ~\sum n \le 1\,000~, ~\sum m \le 1\,000~ |
| 3 | ~1750~ | Không có ràng buộc gì thêm |
| Tổng | ~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
Trong ví dụ thứ nhất, Aqua có thể đến thành phố ~2~ chậm nhất vào thời điểm ~10~ theo kế hoạch sau:
Bỏ qua chuyến bay ~1~, làm thủ tục chuyến bay ~2~ ở thời điểm ~2~.
Nếu chuyến bay ~2~ không bị hủy, Aqua đáp xuống thành phố ~2~ ở thời điểm ~10~.
Ngược lại, Aqua làm thủ tục chuyến bay ~4~. Chuyến bay này chắc chắn không bị hủy do chuyến bay ~2~ đã bị hủy, do đó Aqua đáp xuống thành phố ~2~ ở thời điểm ~4~.
Lưu ý rằng, nếu Aqua không làm thủ tục cho chuyến bay ~2~ thì cô không thể đảm bảo đến được thành phố ~2~, do chuyến bay ~3~ và ~4~ khởi hành cùng giờ và cô chỉ có thể chọn làm thủ tục cho một trong hai chuyến bay này (và chuyến bay cô chọn luôn có thể bị hủy).
Dưới đây là minh họa cho ví dụ đầu tiên:
Cạnh màu xanh là chuyến bay của hãng ~\color{blue}{Pekoland\,Airlines}~.
Cạnh màu đỏ là chuyến bay của hãng ~\color{red}{PekoJet\,Air}~.
Số màu xanh lá cây trên cạnh là thời điểm cất cánh của chuyến bay ~\color{green}{x_i}~.
Số màu cam trên cạnh là thời điểm hạ cánh của chuyến bay ~\color{orange}{y_i}~.
Minh họa cho ví dụ đầu tiên
Trong ví dụ thứ hai, Aqua có thể chọn bay tới thành phố ~2~, ~3~, hoặc ~4~ ở thời điểm ~5~. Tuy nhiên, bất kể cô chọn thành phố nào, chuyến bay duy nhất nối thành phố đó và thành phố ~5~ đều có thể bị hủy. Do đó, đáp án là ~-1~.
Minh họa cho ví dụ thứ hai
Trong ví dụ thứ ba, hãng PekoJet Air đảm bảo rằng không quá 2 chuyến bay sẽ bị hủy. Aqua có thể đến được thành phố ~4~ muộn nhất tại thời điểm ~7~.
Tại thành phố ~1~, thời điểm ~0~, Aqua có thể thử làm thủ tục cho chuyến bay của hãng PekoJet Air.
Nếu chuyến bay không bị hủy, Aqua có thể đi tiếp đến thành phố ~4~ bằng chuyến bay của hãng Pekoland Airlines tại thời điểm ~6~. Aqua đã đến đích.
Nếu chuyến bay bị hủy, Aqua đến thành phố ~3~ tại thời điểm ~3~ với chuyến bay của hãng Pekoland Airlines.
Khi ở thành phố ~3~ ở thời điểm ~3~, Aqua có thể thử chuyến bay của hãng PekoJet Air đến thành phố ~2~.
Nếu chuyến bay không bị hủy, Aqua có thể đi tiếp đến thành phố ~4~ bằng chuyến bay của hãng Pekoland Airlines tại thời điểm ~6~. Aqua đã đến đích.
Nếu chuyến bay bị hủy, Aqua ở lại thành phố ~3~ và xét chuyến bay đến thành phố ~4~.
Đến lúc này, PekoJet Air đã hủy 2 chuyến bay, do đó hãng không thể hủy thêm chuyến bay nào nữa.
Aqua có thể bắt chuyến bay bất kỳ của hãng PekoJet Air đến thành phố ~4~ tại thời điểm ~7~. Aqua đã đến đích.
Minh họa cho ví dụ thứ ba
Bình luận
ahjhj tao bi g.a.y va ng0k nhe
uk toi bi ng0k nhe ahjhj
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.