กำหนดจำนวนเต็ม $n, m > 0$ รวมถึงจำนวนเต็ม $a_1, a_2, \dots, a_n \in \{-1, 0, 1, \dots, m - 1\}$ จงสร้างต้นไม้ $T$ ที่มีจุดยอด $n$ จุด คือ $V = \{v_1, v_2, \dots, v_n\}$ ตามเงื่อนไขต่อไปนี้: สำหรับแต่ละจุดยอด $v_i$ ที่ $a_i \ne -1$ เศษเหลือของดีกรี $\deg_T(v_i)$ เมื่อหารด้วย $m$ จะต้องเท่ากับ $a_i$ หาก $a_i = -1$ จะไม่มีข้อจำกัดเกี่ยวกับดีกรีของ $v_i$

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $t$ คือจำนวนชุดข้อมูลทดสอบ ($1 \le t \le 5 \cdot 10^5$) สำหรับแต่ละชุดข้อมูลทดสอบ:

บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ $n$ และ $m$ ซึ่งแทนจำนวนจุดยอดในต้นไม้และตัวมอดุลัส ($1 \le n \le 5 \cdot 10^5$; $1 \le m \le 2 \cdot 10^9$)

บรรทัดถัดไปประกอบด้วยจำนวนเต็ม $n$ ตัว คือ $a_1, a_2, \dots, a_n$ ซึ่งแทนเศษเหลือที่ต้องการ ($-1 \le a_i < m$)

ผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบไม่เกิน $5 \cdot 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ หากมีต้นไม้ที่มีจุดยอด $n$ จุดดังกล่าวอยู่จริง ให้แสดงผล "YES" (ตัวพิมพ์ใหญ่หรือเล็กก็ได้) ตามด้วย $n - 1$ บรรทัด แต่ละบรรทัดมีจำนวนเต็มสองตัวซึ่งแทนจุดปลายของแต่ละเส้นเชื่อม มิฉะนั้นให้แสดงผล "NO" (ตัวพิมพ์ใหญ่หรือเล็กก็ได้)

ตัวอย่าง

ข้อมูลนำเข้า

6
1 5
0
2 3
1 1
5 4
0 1 1 1 1
6 2
1 0 0 0 0 1
3 2
1 1 1
4 10
3 3 1 1

ข้อมูลส่งออก

YES
YES
1 2
YES
1 2
1 3
1 4
1 5
YES
1 2
2 3
3 4
4 5
5 6
NO
NO

หมายเหตุ

ในชุดข้อมูลทดสอบแรก เราได้รับมอบหมายให้สร้างต้นไม้ที่มีจุดยอด $n = 1$ จุด, $m = 5$ และอาเรย์ของเศษเหลือดีกรี $b = [0]$ เมื่อมีเพียงจุดยอดเดียวจึงไม่สามารถมีเส้นเชื่อมได้ ดังนั้นจึงมีต้นไม้ที่เป็นไปได้เพียงแบบเดียวเท่านั้น คือจุดยอดเดี่ยวที่มีดีกรี $0$ เนื่องจาก $0 \bmod 5 = 0$ จึงตรงตามข้อกำหนด ดังนั้นคำตอบคือ "YES"

ในชุดข้อมูลทดสอบที่สอง เราต้องการต้นไม้บนจุดยอด $n = 2$ จุด โดยที่ $m = 3$ และเศษเหลือ $b = [1, 1]$ ซึ่งหมายความว่าดีกรีทั้งสองต้องสมภาคกับ $1$ มอดูโล $3$ บนจุดยอดสองจุดมีต้นไม้เพียงต้นเดียวเท่านั้น คือเส้นเชื่อมเดี่ยว $1-2$ ดีกรีของมันคือ $(1, 1)$ และ $1 \bmod 3 = 1$ จริง ดังนั้นคำตอบคือ "YES" และการพิมพ์ "1 2" จึงถูกต้อง

ในชุดข้อมูลทดสอบที่สาม เราต้องการ $n = 5$, $m = 4$ โดยมีเศษเหลือ $b = [0, 1, 1, 1, 1]$: จุดยอดแรกต้องมีดีกรีที่หารด้วย $4$ ลงตัว ในขณะที่จุดยอดอีกสี่จุดต้องมี $\text{degree} \equiv 1 \pmod 4$ การสร้างที่เป็นธรรมชาติคือกราฟดาวที่มีจุดศูนย์กลางอยู่ที่จุดยอด $1$: เชื่อมต่อ $1$ เข้ากับทุกจุดยอดอื่น จะได้ $\deg(1) = 4$ และ $4 \bmod 4 = 0$ ในขณะที่แต่ละจุดยอดของ $2, 3, 4, 5$ มีดีกรี $1$ และ $1 \bmod 4 = 1$ ดังนั้นคำตอบคือ "YES" และเส้นเชื่อม "1 2", "1 3", "1 4", "1 5" ใช้ได้

ในชุดข้อมูลทดสอบที่สี่ เราต้องการต้นไม้ที่มี $n = 6$, $m = 2$, เศษเหลือ $b = [1, 0, 0, 0, 0, 1]$ กล่าวคือจุดปลายต้องมีดีกรีคี่ และจุดยอดตรงกลางสี่จุดต้องมีดีกรีคู่ ในมอดูโล $2$ นี่เป็นเพียงข้อจำกัดเรื่องภาวะคู่คี่ วิถีเชิงเดียว $1-2-3-4-5-6$ เข้ากันได้อย่างสมบูรณ์แบบ: จุดยอด $1$ และ $6$ มีดีกรี $1$ (คี่) และจุดยอด $2, 3, 4, 5$ มีดีกรี $2$ (คู่) ดังนั้นคำตอบคือ "YES" และเส้นเชื่อมของวิถีนี้ถูกต้อง

ในชุดข้อมูลทดสอบที่ห้า เราได้รับมอบหมายให้สร้างกราฟ (และโดยเฉพาะอย่างยิ่งคือต้นไม้) บน $n = 3$ โดยที่ $m = 2$ และ $b = [1, 1, 1]$ ดังนั้นทุกจุดยอดต้องมีดีกรีคี่ ซึ่งเป็นไปไม่ได้: ในกราฟไม่ระบุทิศทางใดๆ จำนวนจุดยอดที่มีดีกรีคี่จะเป็นจำนวนคู่เสมอ ดังนั้นการมีดีกรีคี่สามจุดจึงไม่สามารถเกิดขึ้นได้สำหรับเซตของเส้นเชื่อมใดๆ ดังนั้นผลการตัดสินคือ "NO"

ในชุดข้อมูลทดสอบที่หก เรามี $n = 4$, $m = 10$, $b = [3, 3, 1, 1]$ เนื่องจาก $m > n - 1 = 3$ เศษเหลือมอดูโล $10$ จึงเท่ากับตัวดีกรีเอง ดังนั้นเราจึงต้องการ $\deg = [3, 3, 1, 1]$ พอดี นั่นบังคับให้จุดยอดสองจุดต้องประชิดกับจุดยอดอื่นทั้งหมด (ดีกรี $3$ ในกราฟ $4$ จุดยอด) และเมื่อ $n > 2$ คู่ของจุดยอดดังกล่าวจะก่อให้เกิดวัฏจักรร่วมกับจุดยอดที่สามใดๆ อย่างหลีกเลี่ยงไม่ได้ ต้นไม้ไม่สามารถมีวัฏจักรได้ ดังนั้นผลการตัดสินจึงเป็น "NO" เช่นกัน