תיאור הבעיה
כמובן, זו בעיה.
זוהי בעיה אינטראקטיבית. נתון לך גרף לא מכוון ולא ידוע עם $n$ צמתים ו-$m$ קשתות, ללא קשתות מקבילות או לולאות עצמיות. בכל פעם, תוכל לשאול את ספריית האינטראקציה את השאלה הבאה:
- בהינתן קבוצת צמתים $S \subseteq \{1, 2, \dots, n\}$, שאל האם קבוצת צמתים זו היא קבוצה בלתי תלויה.
כאן, קבוצה בלתי תלויה משמעותה שאין קשת בין אף שני צמתים שונים בקבוצה $S$.
המטרה שלך היא לקבוע את כל קבוצת הקשתות של הגרף באמצעות לא יותר מ-$M = n + m(2 + \lceil\log_2 n\rceil)$ שאילתות.
שים לב שאינך יודע את ערכו של $m$ מראש, וספריית האינטראקציה היא אדפטיבית, כלומר הגרף אינו קבוע מההתחלה, אלא יותאם באופן דינמי בהתאם לשאילתות שלך.
קלט
השורה הראשונה מכילה מספר שלם $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
הערה
הדוגמה מדגימה תהליך אינטראקטיבי של שאילתה לגבי קיומה של כל קשת בנפרד.