Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Interactive Hackable ✓
Statistics

Есептің шарты

Әрине, бұл есеп.

Бұл интерактивті есеп. Сізге $n$ төбесі және $m$ қыры бар, еселі қырлары мен ілмектері жоқ белгісіз бағытталмаған граф берілген. Әр жолы сіз интерактивті кітапханаға келесі сұрақты қоя аласыз:

  • $S \subseteq \{1, 2, \dots, n\}$ төбелер жиыны берілгенде, бұл төбелер жиыны тәуелсіз жиын болып табыла ма деп сұрау.

Мұнда тәуелсіз жиын дегеніміз — $S$ жиынындағы кез келген екі түрлі төбенің арасында қыр жоқ екенін білдіреді.

Сіздің мақсатыңыз — $M = n + m(2 + \lceil\log_2 n\rceil)$ сұраныстан аспайтын сұраныс жасап, графтың барлық қырлар жиынын анықтау.

Алдын ала $m$ мәнін білмейтініңізді және интерактивті кітапхананың бейімделгіш (adaptive) екенін ескеріңіз, яғни граф басынан бастап бекітілмеген, бірақ сіздің сұраныстарыңызға сәйкес динамикалық түрде өзгертіліп отырады.

Кіріс деректер

Бірінші жолда тест жиынтықтарының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 100$) берілген.

Әрбір тест жиынтығы үшін бір жолда белгісіз бағытталмаған графтың төбелер санын білдіретін бір бүтін сан $n$ ($1 \le n \le 500$) берілген.

Барлық тест жиынтықтары бойынша $n$ қосындысы $500$-ден аспайтынына, $0 \le m \le 500$ екеніне және $m$ қосындысы $500$-ден аспайтынына кепілдік беріледі.

Өзара әрекеттесу

Сұраныс жасау қажет болғанда, бір жолды шығарыңыз:

? k v_1 v_2 ... v_k

мұндағы $k$ төбелер жиынының өлшемін білдіреді, ал $v_1, v_2, \dots, v_k$ — сіз сұрап отырған жиындағы төбелердің нөмірлері, олардың барлығы өзара әртүрлі.

Интерактивті кітапхана бүтін сан қайтарады: егер төбелер жиыны тәуелсіз жиын болса $1$; әйтпесе $0$.

Графтың барлық қырларын анықтаған соң, бір жолды шығарыңыз:

! m u_1 v_1 u_2 v_2 ... u_m v_m

мұндағы $m$ — бағытталмаған графтағы қырлар саны, ал $(u_i, v_i)$ графтағы қырды білдіреді. Қырларды кез келген ретпен шығаруға болады.

Осыдан кейін, егер қалған тест жиынтықтары болмаса, бағдарламаңыз дереу аяқталуы тиіс; әйтпесе ол келесі тест жиынтығына өтуі керек.

Мысалдар

Кіріс 1

1
4
0
1
0
0
1
0

Шығыс 1

? 2 1 2
? 2 1 3
? 2 1 4
? 2 2 3
? 2 2 4
? 2 3 4
! 4 1 2 2 3 3 4 1 4

Ескертпе

Мысалда әрбір қырдың бар-жоғын жеке-жеке сұрау арқылы өтетін өзара әрекеттесу процесі көрсетілген.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1842EditorialOpenNew Editorial for Problem #18123wangmaruiView

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.