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$ لإضافتها إلى الرسم البياني لضمان ألا يتجاوز عدد المركبات المتصلة في الرسم البياني $x$.

على الرغم من أن الأمر ليس واضحًا على الفور، إلا أن هناك أوراقًا بحثية تشير إلى أن الحد الأدنى لعدد تلوين شجرة الامتداد هو مسألة 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.