Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.