Есептің шарты
Әрине, бұл есеп.
Бұл интерактивті есеп. Сізге $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
Ескертпе
Мысалда әрбір қырдың бар-жоғын жеке-жеке сұрау арқылы өтетін өзара әрекеттесу процесі көрсетілген.