JOO PIPI

View as PDF

Submit solution


Points: 0.74 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
CERC 2010; Người dịch: Trần Quốc Ðạt
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bao quanh thủ đô là ~n~ hồ lớn, đánh số từ ~1~ đến ~n~. Ban đầu các hồ đều đầy nước. Theo dự báo thời tiết những ngày tới sẽ có các trận mưa lớn, mỗi trận mưa diễn ra trên vùng của một hồ. Nếu hồ cạn, mưa sẽ làm hồ đầy nước, nếu hồ đang đầy nước, mưa sẽ làm nước tràn bờ gây ngập lụt ở thủ đô. May mắn là có một con rồng biệt danh Joo PiPi. Vào ngày không mưa katejordan_ts có thể dắt Joo PiPi ra một hồ nào đó và trong ngày rồng có thể uống cạn hồ nước này. Cơ quan dự báo thời tiết đưa ra dự báo cho ~m~ ngày dưới dạng các số ~t_{1}, t_{2}, \dots, t_{m}~, trong đó ~t_{i}~ thuộc đoạn ~[0~, ~n]~. Nếu ~t_{i}~ thuộc đoạn ~[1~, ~n]~ có nghĩa là sẽ có mưa trên hồ ~t_{i}~ vào ngày ~i~, nếu ~t_{i} = 0~ là ngày ~i~ không có mưa.

Yêu cầu : Cho ~n~, ~m~ và các ~t_{i}~ ~(1 \leq n~, ~m \leq 10^{6}~, ~i = 1 \dots m)~. Hãy xác định xem có tồn tại lịch cho Joo PiPi hút nước tránh lụt được hay không và đưa ra câu trả lời "YES" hoặc "NO". Nếu có lịch hút nước thì đưa ra ở dòng tiếp theo các số nguyên ~l_{1}~, ~l_{2}~, ..., ~l _ p~, trong đó ~p~ là số ngày không mưa, ~l _ j~ thuộc đoạn ~[0~, ~n]~. Nếu ~l _ j \neq 0~ có nghĩa là cần hút nước ở hồ ~l _ j~ trong ngày không mưa thứ ~j~.

Input

  • Dòng đầu tiên chứa số nguyên ~q~ -- số lượng tests ~(1 \leq q \leq 40)~

  • Mỗi test cho trên ~2~ dòng:

    1. Dòng thứ nhất chứa các số nguyên ~n~ và ~m~,
    2. Dòng thứ ~2~ chứa ~m~ số nguyên ~t_{1}~, ~t_{2}~, ..., ~t_{m}~.

Output

Với mỗi test bao gồm:

  • Dòng thứ nhất chứa thông báo " YES " hoặc " NO ",
  • Nếu kết quả là " YES " thì ở dòng thứ ~2~ đưa ra các số nguyên ~l _ 1~, ~l _ 2~, ..., ~l _ p~.

Test đảm bảo chỉ có ~1~ đáp án

Sample Input

1
2 4
0 1 0 2

Sample Output

YES
1 2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.