Tajian กำลังแก้ปัญหาต่อไปนี้:
กำหนดกราฟที่มี $n$ จุด โดยกราฟเริ่มต้นไม่มีเส้นเชื่อมใดๆ Tajian มีเส้นเชื่อมจำนวนหนึ่งที่จะเพิ่มเข้าไปในกราฟ และเขาได้แบ่งเส้นเชื่อมเหล่านี้ออกเป็น $k$ กลุ่ม โดยที่กลุ่มที่ $i$ ประกอบด้วยเส้นเชื่อม $c_i$ เส้น สำหรับแต่ละ $x \in [1, n]$ Tajian ต้องการทราบจำนวนกลุ่มของเส้นเชื่อมที่น้อยที่สุดที่เขาต้องเลือกจาก $k$ กลุ่มนี้เพื่อเพิ่มเข้าไปในกราฟ เพื่อให้มั่นใจว่าจำนวนส่วนประกอบที่เชื่อมโยงกัน (connected components) ในกราฟจะไม่เกิน $x$
แม้ว่ามันจะไม่ชัดเจนในทันที แต่มีงานวิจัยที่ระบุว่าจำนวนสีที่น้อยที่สุดของต้นไม้แผ่ทั่ว (spanning tree) เป็นปัญหา NPC อย่างไรก็ตาม Tajian ไม่ทราบเรื่องนี้ ดังนั้นเขาจึงต้องการให้คุณช่วยเขาแก้ปัญหานี้
ข้อมูลนำเข้า
หนึ่งชุดทดสอบประกอบด้วยข้อมูลหลายชุด
บรรทัดแรกของข้อมูลนำเข้าคือจำนวนชุดข้อมูล $T$ ($1 \le T \le 10^3$) แทนจำนวนชุดข้อมูลในชุดทดสอบนี้
สำหรับแต่ละชุดข้อมูล บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n, k$ ($2 \le n \le 16, 1 \le k \le 200$) แทนจำนวนจุดและจำนวนกลุ่มของเส้นเชื่อม
ส่วนถัดไปอธิบายข้อมูลของเส้นเชื่อมทั้ง $k$ กลุ่ม สำหรับกลุ่มของเส้นเชื่อมที่ $i$ บรรทัดแรกประกอบด้วยจำนวนเต็ม $c_i$ ($1 \le c_i \le 200$) แทนจำนวนเส้นเชื่อมในกลุ่มนี้ อีก $c_i$ บรรทัดถัดไปแต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวน $u, v$ ($1 \le u, v \le n, u \neq v$) แทนเส้นเชื่อมในกลุ่มนี้
สำหรับหนึ่งชุดข้อมูล รับประกันว่า $\sum c_i \le 200$ สำหรับข้อมูลทั้งหมด รับประกันว่า $\sum 2^n \le 2^{16}$
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูล ให้แสดงผลหนึ่งบรรทัดที่มีจำนวนเต็ม $n$ จำนวน โดยจำนวนเต็มตัวที่ $i$ แทนคำตอบเมื่อ $x = i$
หากไม่สามารถรับประกันได้ว่าจำนวนส่วนประกอบที่เชื่อมโยงกันจะไม่เกิน $i$ ไม่ว่าในกรณีใดๆ ให้แสดงผล "-1"
ตัวอย่าง
ข้อมูลนำเข้า 1
4 3 3 1 1 2 1 2 3 1 1 3 4 3 1 2 3 2 1 2 1 3 1 3 4 6 2 3 1 2 3 4 5 6 2 2 3 4 5 4 2 1 2 3 2 1 3 1 2
ข้อมูลส่งออก 1
2 1 0 2 1 1 0 2 2 1 1 1 0 -1 1 1 0