Multiple Lamps (Codeforces 1909E)
Tags: Math, bitmasks

Kid2Will - Fire Aura⠀You have $$$n$$$ lamps, numbered from $$$1$$$ to $$$n$$$. Initially, all the lamps are turned off.You also have $$$n$$$ buttons. The $$$i$$$-th button toggles all the lamps whose index is a multiple of $$$i$$$. When a lamp is toggled, if it was off it turns on, and if it was on it turns off.You have to press some buttons according to the following rules.  You have to press at least one button.  You cannot press the same button multiple times.  You are given $$$m$$$ pairs $$$(u_i, v_i)$$$. If you press the button $$$u_i$$$, you also have to press the button $$$v_i$$$ (at any moment, not necessarily after pressing the button $$$u_i$$$). Note that, if you press the button $$$v_i$$$, you don't need to press the button $$$u_i$$$. You don't want to waste too much electricity. Find a way to press buttons such that at the end at most $$$\lfloor n/5 \rfloor$$$ lamps are on, or print $$$-1$$$ if it is impossible.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) — the number of lamps and the number of pairs, respectively.Each of the next $$$m$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$). If you press the button $$$u_i$$$, you also have to press the button $$$v_i$$$. It is guaranteed that the pairs $$$(u_i, v_i)$$$ are distinct.It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output: For each test case:   If there is no choice of buttons that makes at most $$$\lfloor n/5 \rfloor$$$ lamps on at the end, output a single line containing $$$-1$$$.  Otherwise, output two lines. The first line should contain an integer $$$k$$$ ($$$1 \le k \le n$$$) — the number of pressed buttons. The second line should contain $$$k$$$ integers $$$b_1, b_2, \dots, b_k$$$ ($$$1 \le b_i \le n$$$) — the indices of the pressed buttons (in any order). The $$$b_i$$$ must be distinct, and at the end at most $$$\lfloor n/5 \rfloor$$$ lamps must be turned on. 

Note: In the first test case, you need to turn at most $$$\lfloor 4/5 \rfloor$$$ lamps on, which means that no lamp can be turned on. You can show that no choice of at least one button turns $$$0$$$ lamps on.In the second test case, you can press buttons $$$3$$$, $$$5$$$, $$$1$$$, $$$2$$$.  Initially, all the lamps are off;  after pressing button $$$3$$$, the lamps whose index is a multiple of $$$3$$$ (i.e., $$$3$$$) are toggled, so lamp $$$3$$$ is turned on;  after pressing button $$$5$$$, the lamps whose index is a multiple of $$$5$$$ (i.e., $$$5$$$) are toggled, so lamps $$$3$$$, $$$5$$$ are turned on;  after pressing button $$$1$$$, the lamps whose index is a multiple of $$$1$$$ (i.e., $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$) are toggled, so lamps $$$1$$$, $$$2$$$, $$$4$$$ are turned on;  after pressing button $$$2$$$, the lamps whose index is a multiple of $$$2$$$ (i.e., $$$2$$$, $$$4$$$) are toggled, so lamp $$$1$$$ is turned on. This is valid because   you pressed at least one button;  you pressed all the buttons at most once;  you pressed button $$$u_2 = 5$$$, which means that you had to also press button $$$v_2 = 1$$$: in fact, button $$$1$$$ has been pressed;  at the end, only lamp $$$1$$$ is on. In the third test case, pressing the buttons $$$8$$$, $$$9$$$, $$$10$$$ turns only the lamps $$$8$$$, $$$9$$$, $$$10$$$ on.

Sample Inputs:
4
4 0
5 2
4 1
5 1
15 9
7 8
8 9
9 10
10 9
11 1
12 2
13 3
14 4
15 5
5 4
1 2
2 3
3 4
4 5

Sample Outputs:
-1
4
3 5 1 2
3
8 9 10
1
5

Solution (Python):
""""""

def test():
    for n in range(1, 50):
        if floor(n ** 0.5) <= floor(n / 5):
            print(n)
    return

def main():
    possible_masks = [[] for _ in range(20)]
    for n in range(1, 20):
        for mask in range(1, 1 << n):
            arr = [0] * (n + 1)
            for i in range(n):
                if mask & 1 << i > 0:
                    v = i + 1
                    for j in range(v, n + 1, v):
                        arr[j - 1] ^= 1
            if sum(arr) <= floor(n / 5):
                possible_masks[n].append(mask)
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        adj = [[] for __ in range(n + 1)]
        for __ in range(m):
            (u, v) = readIntArr()
            adj[u].append(v)
        if n >= 20:
            k = n
            ans = list(range(1, n + 1))
            allans.append([k])
            allans.append(ans)
        else:
            ans = -1
            for mask in possible_masks[n]:
                ok = True
                arr = []
                for i in range(n):
                    if mask & 1 << i > 0:
                        u = i + 1
                        arr.append(u)
                        for v in adj[u]:
                            j = v - 1
                            if mask & 1 << j == 0:
                                ok = False
                                break
                        if not ok:
                            break
                if ok:
                    ans = arr
                    break
            if ans == -1:
                allans.append([-1])
            else:
                k = len(ans)
                allans.append([k])
                allans.append(ans)
    multiLineArrayOfArraysPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys
import io
import os
from string import *
from re import *
from collections import *
from heapq import *
from bisect import *
from copy import *
from random import *
from itertools import *
from functools import *
from typing import *
MOD = 998244353
inf = 1 << 60
candis = [[], [], [], [], [], [4, 8, 10, 16, 23], [8, 16, 32, 36, 42, 55], [8, 16, 32, 36, 42, 64, 119], [16, 32, 36, 42, 64, 119, 128, 136], [16, 32, 42, 64, 119, 128, 136, 256, 292], [8, 16, 32, 36, 42, 58, 64, 93, 96, 103, 119, 128, 136, 160, 168, 192, 200, 256, 260, 288, 292, 320, 356, 384, 392, 420, 428, 512, 522, 528, 544, 554, 560, 567, 576, 592, 599, 618, 631, 640, 648, 656, 664, 674, 682, 759, 767, 768, 782, 784, 804, 810, 820, 851, 887], [8, 16, 32, 36, 42, 58, 64, 96, 128, 136, 160, 168, 192, 200, 256, 260, 288, 292, 320, 356, 384, 392, 420, 428, 512, 522, 528, 544, 554, 560, 576, 592, 618, 631, 640, 648, 656, 664, 674, 682, 768, 782, 784, 804, 810, 820, 1024, 1056, 1088, 1117, 1127, 1143, 1152, 1160, 1280, 1316, 1536, 1552, 1578, 1591, 1623, 1655, 1783, 1791, 1875, 1911], [16, 32, 36, 64, 128, 136, 168, 192, 256, 292, 320, 356, 384, 420, 512, 522, 528, 554, 576, 592, 631, 640, 656, 674, 768, 784, 804, 820, 1024, 1088, 1127, 1143, 1152, 1280, 1316, 1536, 1552, 1591, 1655, 1783, 1875, 1911, 2048, 2056, 2080, 2090, 2106, 2112, 2144, 2176, 2184, 2208, 2248, 2304, 2308, 2336, 2340, 2440, 2476, 2560, 2576, 2592, 2602, 2608, 2666, 2696, 2712, 2730, 2830, 2858, 3072, 3104, 3165, 3208, 3626, 3671, 3703, 3839], [16, 32, 36, 64, 128, 136, 168, 192, 256, 292, 320, 356, 384, 420, 512, 522, 528, 554, 576, 592, 640, 656, 674, 768, 784, 804, 820, 1024, 1088, 1152, 1280, 1316, 1536, 1552, 1655, 2048, 2056, 2080, 2090, 2106, 2112, 2144, 2176, 2184, 2208, 2248, 2304, 2308, 2336, 2340, 2440, 2476, 2560, 2576, 2592, 2602, 2608, 2666, 2696, 2712, 2730, 2830, 2858, 3072, 3104, 3208, 3626, 4096, 4160, 4224, 4352, 4388, 4608, 4624, 4727, 5120, 5223, 5239, 5687, 5751, 5879, 5971, 6007, 6144, 6176, 6280, 6698, 7261, 7767, 7799, 7935], [16, 32, 36, 64, 128, 136, 168, 256, 292, 384, 420, 512, 528, 640, 656, 768, 784, 804, 820, 1024, 1152, 1280, 1316, 1536, 1552, 2048, 2056, 2080, 2176, 2184, 2208, 2304, 2308, 2336, 2340, 2440, 2476, 2560, 2576, 2592, 2602, 2608, 2666, 2696, 2712, 3072, 3104, 3208, 4096, 4224, 4352, 4388, 4608, 4624, 5120, 5687, 5751, 6144, 6176, 6280, 7261, 8192, 8256, 8320, 8384, 8448, 8484, 8512, 8548, 8704, 8714, 8720, 8746, 8768, 8784, 8866, 9216, 9280, 9847, 10240, 10272, 10282, 10298, 10304, 10336, 10376, 10440, 10794, 10922, 11022, 11050, 11818, 12288, 12352, 12919, 13415, 13431, 13943, 14071, 14163, 14199, 14890, 15959, 15991, 16127], [], [16, 32, 36, 64, 128, 136, 168, 256, 288, 292, 308, 320, 384, 392, 424, 512, 522, 528, 544, 554, 564, 576, 586, 618, 640, 648, 674, 680, 738, 768, 784, 804, 820, 1024, 1056, 1088, 1152, 1160, 1192, 1280, 1316, 1536, 1552, 1792, 1844, 2048, 2056, 2080, 2090, 2112, 2144, 2154, 2176, 2184, 2208, 2216, 2248, 2304, 2308, 2336, 2340, 2440, 2476, 2560, 2576, 2592, 2602, 2608, 2666, 2696, 2712, 2816, 2836, 2848, 2858, 2868, 2922, 2952, 3004, 3072, 3104, 3208, 3328, 3360, 3464, 3584, 3616, 3626, 3690, 3720, 4096, 4128, 4160, 4224, 4232, 4264, 4352, 4388, 4608, 4624, 4864, 4916, 5120, 5159, 5223, 5376, 5632, 5687, 5751, 5907, 5971, 6144, 6176, 6280, 6400, 6432, 6536, 6656, 6688, 6698, 6762, 6792, 7168, 7200, 7261, 7304, 7545, 7757, 8192, 8202, 8224, 8234, 8256, 8288, 8320, 8328, 8354, 8360, 8384, 8392, 8424, 8448, 8484, 8512, 8548, 8704, 8714, 8720, 8746, 8768, 8784, 8866, 8960, 8970, 9002, 9012, 9024, 9076, 9122, 9216, 9280, 9319, 9472, 9536, 9728, 9738, 9770, 9792, 9847, 9890, 10067, 10240, 10272, 10282, 10298, 10304, 10336, 10376, 10440, 10496, 10526, 10528, 10538, 10560, 10592, 10632, 10696, 10752, 10762, 10784, 10794, 10816, 10848, 10858, 10882, 10888, 10914, 10922, 10952, 11022, 11050, 11264, 11296, 11306, 11328, 11360, 11400, 11464, 11818, 12074, 12288, 12352, 12391, 12544, 12608, 12800, 12810, 12842, 12864, 12919, 12962, 13139, 13312, 13376, 13415, 13431, 13651, 13671, 13907, 13927, 13943, 14163, 14199, 14336, 14368, 14378, 14400, 14432, 14472, 14536, 14890, 15146, 15431, 15463, 15599, 15914, 15959, 15991, 16127, 16211, 16243, 16347, 16384, 16400, 16416, 16420, 16448, 16512, 16520, 16552, 16640, 16644, 16656, 16676, 16740, 16780, 16804, 16812, 16896, 16912, 16932, 16944, 16976, 17040, 17048, 17080, 17152, 17168, 17188, 17204, 17408, 17424, 17444, 17664, 17700, 17920, 17936, 17975, 18039, 18192, 18212, 18432, 18436, 18448, 18464, 18468, 18480, 18490, 18554, 18568, 18584, 18604, 18688, 18692, 18720, 18724, 18824, 18860, 18944, 18960, 18976, 18986, 18992, 19050, 19080, 19096, 19204, 19214, 19216, 19236, 19248, 19278, 19352, 19372, 19456, 19488, 19549, 19592, 19716, 19748, 19884, 19984, 20016, 20120, 20480, 20496, 20516, 20736, 20772, 20992, 21008, 21047, 21111, 21264, 21284, 21504, 21559, 21597, 21623, 21629, 21717, 21796, 22032, 22071, 22135, 22327, 22391, 22528, 22560, 22621, 22664, 22788, 22820, 22956, 23056, 23088, 23192, 23645, 23901, 24087, 24119, 24151, 24157, 24183, 24255, 24319, 24576, 24592, 24602, 24612, 24634, 24640, 24656, 24676, 24754, 24832, 24868, 24896, 24932, 25088, 25098, 25104, 25130, 25152, 25168, 25207, 25250, 25358, 25360, 25380, 25390, 25424, 25444, 25478, 25600, 25664, 25719, 25892, 25956, 26128, 26192, 26231, 26487, 26624, 26656, 26666, 26682, 26688, 26720, 26760, 26824, 26884, 26894, 26916, 26938, 26948, 26980, 27052, 27116, 27150, 27152, 27178, 27184, 27194, 27216, 27248, 27288, 27352, 27406, 27434, 27706, 28202, 28247, 28279, 28415, 28430, 28672, 28736, 28791, 28964, 29028, 29200, 29264, 29303, 29559, 29799, 29815, 30019, 30071, 30263, 30295, 30327, 30431, 30455, 30463, 30547, 30583, 30778, 31274, 31319, 31351, 31487, 31502, 31773, 31831, 31837, 31863, 31999, 32343, 32375, 32511, 32599, 32631, 32767, 32768, 32776, 32800, 32808, 32832, 32896, 32904, 32928, 32936, 32960, 33024, 33060, 33152, 33188, 33280, 33296, 33408, 33424, 33536, 33588, 33664, 33716, 33792, 33920, 34048, 34176, 34304, 34432, 34816, 34824, 34848, 34944, 34952, 34976, 35072, 35080, 35104, 35200, 35208, 35232, 35328, 35336, 35360, 35370, 35434, 35456, 35464, 35488, 35498, 35562, 35840, 35848, 35872, 35968, 35976, 36000, 36864, 36992, 37120, 37248, 37376, 37504, 37888, 38016, 38912, 38920, 38944, 39040, 39048, 39072, 40960, 41024, 41088, 41152, 41216, 41280, 41344, 41408, 41472, 41482, 41506, 41514, 41536, 41600, 41610, 41634, 41642, 41664, 41984, 42048, 42112, 42176, 43008, 43016, 43040, 43050, 43072, 43080, 43104, 43136, 43144, 43168, 43178, 43200, 43208, 43232, 43562, 43690, 43818, 43946, 44586, 44714, 45056, 45120, 45184, 45248, 46183, 46311, 46711, 46839, 46931, 47059, 47658, 47786, 49152, 49168, 49188, 49280, 49296, 49316, 49408, 49444, 49536, 49572, 49664, 49680, 49792, 49808, 49936, 49956, 50064, 50084, 50176, 50304, 50468, 50596, 50704, 50832, 51200, 51208, 51232, 51328, 51336, 51360, 51460, 51492, 51500, 51588, 51620, 51628, 51728, 51736, 51760, 51856, 51864, 51888, 53248, 53376, 53540, 53668, 53776, 53904, 54839, 54903, 54967, 55031, 56413, 56541, 57344, 57408, 57472, 57536, 57636, 57700, 57764, 57828, 57872, 57936, 58000, 58064, 58999, 59127, 59450, 59578, 59946, 60074, 60174, 60302, 62071, 62199, 62583, 62711, 63095, 63223, 63351, 63479, 65111, 65143, 65151, 65239, 65271, 65279], [16, 32, 36, 64, 128, 136, 168, 256, 288, 292, 308, 320, 384, 392, 424, 512, 522, 528, 544, 554, 564, 576, 586, 618, 640, 648, 674, 680, 738, 768, 784, 804, 820, 1024, 1056, 1088, 1152, 1160, 1192, 1280, 1316, 1536, 1552, 1792, 1844, 2048, 2056, 2080, 2090, 2112, 2144, 2154, 2176, 2184, 2208, 2216, 2248, 2304, 2308, 2336, 2340, 2440, 2476, 2560, 2576, 2592, 2602, 2608, 2666, 2696, 2712, 2816, 2836, 2848, 2858, 2868, 2922, 2952, 3004, 3072, 3104, 3208, 3328, 3360, 3464, 3584, 3616, 3626, 3690, 3720, 4096, 4128, 4160, 4224, 4232, 4264, 4352, 4388, 4608, 4624, 4864, 4916, 5120, 5376, 5632, 6144, 6176, 6280, 6400, 6432, 6536, 6656, 6688, 6698, 6762, 6792, 7168, 7200, 7304, 8192, 8202, 8224, 8234, 8256, 8288, 8320, 8328, 8354, 8360, 8384, 8392, 8424, 8448, 8484, 8512, 8548, 8704, 8714, 8720, 8746, 8768, 8784, 8866, 8960, 8970, 9002, 9012, 9024, 9076, 9122, 9216, 9280, 9472, 9536, 9728, 9738, 9770, 9792, 9890, 10240, 10272, 10282, 10298, 10304, 10336, 10376, 10440, 10496, 10526, 10528, 10538, 10560, 10592, 10632, 10696, 10752, 10762, 10784, 10794, 10816, 10848, 10858, 10882, 10888, 10914, 10922, 10952, 11022, 11050, 11264, 11296, 11306, 11328, 11360, 11400, 11464, 11818, 12074, 12288, 12352, 12544, 12608, 12800, 12810, 12842, 12864, 12962, 13312, 13376, 13415, 13943, 14163, 14336, 14368, 14378, 14400, 14432, 14472, 14536, 14890, 15146, 15914, 16384, 16400, 16416, 16420, 16448, 16512, 16520, 16552, 16640, 16644, 16656, 16676, 16740, 16780, 16804, 16812, 16896, 16912, 16932, 16944, 16976, 17040, 17048, 17080, 17152, 17168, 17188, 17204, 17408, 17424, 17444, 17664, 17700, 17920, 17936, 18192, 18212, 18432, 18436, 18448, 18464, 18468, 18480, 18490, 18554, 18568, 18584, 18604, 18688, 18692, 18720, 18724, 18824, 18860, 18944, 18960, 18976, 18986, 18992, 19050, 19080, 19096, 19204, 19214, 19216, 19236, 19248, 19278, 19352, 19372, 19456, 19488, 19592, 19716, 19748, 19884, 19984, 20016, 20120, 20480, 20496, 20516, 20736, 20772, 20992, 21008, 21264, 21284, 21504, 21796, 22032, 22071, 22135, 22528, 22560, 22664, 22788, 22820, 22956, 23056, 23088, 23192, 23645, 24576, 24592, 24602, 24612, 24634, 24640, 24656, 24676, 24754, 24832, 24868, 24896, 24932, 25088, 25098, 25104, 25130, 25152, 25168, 25250, 25358, 25360, 25380, 25390, 25424, 25444, 25478, 25600, 25664, 25892, 25956, 26128, 26192, 26231, 26624, 26656, 26666, 26682, 26688, 26720, 26760, 26824, 26884, 26894, 26916, 26938, 26948, 26980, 27052, 27116, 27150, 27152, 27178, 27184, 27194, 27216, 27248, 27288, 27352, 27406, 27434, 27706, 28202, 28430, 28672, 28736, 28964, 29028, 29200, 29264, 29303, 29815, 30327, 30583, 30778, 31274, 31502, 32343, 32375, 32511, 32768, 32776, 32800, 32808, 32832, 32896, 32904, 32928, 32936, 32960, 33024, 33060, 33152, 33188, 33280, 33296, 33408, 33424, 33536, 33588, 33664, 33716, 33792, 33920, 34048, 34176, 34304, 34432, 34816, 34824, 34848, 34944, 34952, 34976, 35072, 35080, 35104, 35200, 35208, 35232, 35328, 35336, 35360, 35370, 35434, 35456, 35464, 35488, 35498, 35562, 35840, 35848, 35872, 35968, 35976, 36000, 36864, 36992, 37120, 37248, 37376, 37504, 37888, 38016, 38912, 38920, 38944, 39040, 39048, 39072, 40960, 41024, 41088, 41152, 41216, 41280, 41344, 41408, 41472, 41482, 41506, 41514, 41536, 41600, 41610, 41634, 41642, 41664, 41984, 42048, 42112, 42176, 43008, 43016, 43040, 43050, 43072, 43080, 43104, 43136, 43144, 43168, 43178, 43200, 43208, 43232, 43562, 43690, 43818, 43946, 44586, 44714, 45056, 45120, 45184, 45248, 47658, 47786, 49152, 49168, 49188, 49280, 49296, 49316, 49408, 49444, 49536, 49572, 49664, 49680, 49792, 49808, 49936, 49956, 50064, 50084, 50176, 50304, 50468, 50596, 50704, 50832, 51200, 51208, 51232, 51328, 51336, 51360, 51460, 51492, 51500, 51588, 51620, 51628, 51728, 51736, 51760, 51856, 51864, 51888, 53248, 53376, 53540, 53668, 53776, 53904, 57344, 57408, 57472, 57536, 57636, 57700, 57764, 57828, 57872, 57936, 58000, 58064, 59450, 59578, 59946, 60074, 60174, 60302, 63095, 63223, 65536, 65568, 65600, 65664, 65672, 65704, 65792, 65828, 66048, 66064, 66304, 66356, 66560, 66816, 67072, 67584, 67616, 67720, 67840, 67872, 67976, 68096, 68128, 68138, 68202, 68232, 68608, 68640, 68744, 69632, 69888, 70144, 70656, 70695, 70759, 71223, 71287, 71443, 71507, 71680, 71712, 71816, 72797, 73081, 73293, 73728, 73792, 73984, 74048, 74240, 74250, 74282, 74304, 74402, 74752, 74816, 74855, 75383, 75603, 75776, 75808, 75818, 75840, 75872, 75912, 75976, 76330, 76586, 77354, 77824, 77888, 77927, 78455, 78675, 78951, 78967, 79187, 79207, 79443, 79463, 79479, 79699, 79735, 80426, 80967, 80999, 81135, 81495, 81527, 81663, 81747, 81779, 81883, 81920, 81936, 81956, 82176, 82212, 82432, 82448, 82704, 82724, 82944, 83236, 83472, 83511, 83575, 83968, 84000, 84104, 84228, 84260, 84396, 84496, 84528, 84632, 85085, 86016, 86308, 86544, 86583, 86647, 87095, 87133, 87159, 87165, 87253, 87607, 87671, 87863, 87927, 88157, 89181, 89437, 89623, 89655, 89687, 89693, 89719, 89791, 89855, 90112, 90176, 90404, 90468, 90640, 90704, 90743, 91255, 91767, 92023, 92218, 92714, 92942, 93783, 93815, 93951, 94327, 94839, 95095, 95335, 95351, 95555, 95607, 95799, 95831, 95863, 95967, 95991, 95999, 96083, 96119, 96855, 96887, 97023, 97309, 97367, 97373, 97399, 97535, 97879, 97911, 98047, 98135, 98167, 98303, 98304, 98432, 98560, 98688, 98816, 98944, 99328, 99456, 100352, 100360, 100384, 100480, 100488, 100512, 102400, 102528, 106496, 106560, 106624, 106688, 109098, 109226, 111719, 111847, 112247, 112375, 112467, 112595, 114688, 114816, 114980, 115108, 115216, 115344, 120375, 120439, 120503, 120567, 121949, 122077, 124535, 124663, 127607, 127735, 128119, 128247, 128631, 128759, 128887, 129015, 130647, 130679, 130687, 130775, 130807, 130815], [16, 32, 36, 64, 128, 136, 168, 256, 288, 292, 424, 512, 528, 554, 564, 576, 618, 640, 648, 674, 738, 768, 820, 1024, 1088, 1152, 1160, 1280, 1536, 1552, 2048, 2056, 2080, 2090, 2112, 2154, 2176, 2184, 2248, 2304, 2308, 2336, 2440, 2560, 2576, 2592, 2602, 2666, 2696, 2712, 2836, 2848, 3072, 3104, 3208, 3360, 3584, 3626, 3690, 3720, 4096, 4160, 4224, 4232, 4352, 4608, 4624, 5120, 5632, 6144, 6176, 6280, 6432, 6656, 6698, 6762, 6792, 7168, 7304, 8192, 8234, 8256, 8320, 8328, 8354, 8384, 8392, 8448, 8512, 8704, 8714, 8720, 8746, 8768, 8784, 8866, 8970, 9216, 9280, 9728, 9770, 9792, 9890, 10240, 10272, 10282, 10298, 10304, 10336, 10376, 10440, 10528, 10592, 10752, 10794, 10816, 10858, 10888, 10914, 10922, 10952, 11050, 11264, 11306, 11328, 11400, 11464, 11818, 12288, 12352, 12800, 12842, 12864, 12962, 13312, 13376, 13415, 13943, 14336, 14378, 14400, 14472, 14536, 14890, 15914, 16384, 16400, 16420, 16448, 16512, 16520, 16640, 16644, 16676, 16780, 16896, 16912, 16932, 16976, 17040, 17048, 17168, 17188, 17408, 17424, 17444, 17700, 17920, 17936, 18432, 18448, 18464, 18468, 18490, 18554, 18568, 18584, 18604, 18692, 18720, 18724, 18860, 18944, 18960, 18986, 18992, 19050, 19080, 19096, 19204, 19248, 19456, 19592, 19716, 19984, 20120, 20480, 20496, 20516, 20772, 20992, 21008, 21504, 22032, 22071, 22135, 22528, 22664, 22788, 23056, 23192, 23645, 24576, 24592, 24612, 24634, 24640, 24656, 24676, 24754, 24868, 24932, 25088, 25104, 25130, 25152, 25168, 25250, 25390, 25600, 25664, 26128, 26192, 26231, 26624, 26666, 26682, 26688, 26760, 26824, 26884, 26948, 27150, 27152, 27178, 27194, 27216, 27288, 27352, 27406, 27706, 28202, 28672, 28736, 29200, 29264, 29303, 29815, 30327, 30778, 31274, 32375, 32511, 32768, 32776, 32832, 32896, 32904, 32960, 33024, 33152, 33280, 33296, 33408, 33424, 33792, 33920, 34304, 34432, 34816, 34824, 34848, 34944, 34952, 34976, 35104, 35232, 35328, 35336, 35370, 35434, 35456, 35464, 35498, 35562, 35840, 35848, 35968, 35976, 36864, 36992, 37376, 37504, 37888, 38016, 38912, 38920, 39040, 39048, 40960, 41024, 41088, 41152, 41472, 41506, 41514, 41536, 41600, 41634, 41642, 41664, 41984, 42048, 42112, 42176, 43008, 43016, 43050, 43072, 43080, 43136, 43144, 43178, 43200, 43208, 43562, 43690, 44586, 44714, 45056, 45120, 45184, 45248, 47658, 47786, 49152, 49168, 49188, 49280, 49296, 49316, 49444, 49572, 49664, 49680, 49792, 49808, 50176, 50304, 50704, 50832, 51200, 51208, 51328, 51336, 51460, 51588, 51728, 51736, 51856, 51864, 53248, 53376, 53776, 53904, 57344, 57408, 57472, 57536, 57872, 57936, 58000, 58064, 59450, 59578, 59946, 60074, 63095, 63223, 65536, 65600, 65664, 65672, 65792, 66048, 66064, 66560, 67072, 67584, 67616, 67720, 67872, 68096, 68138, 68202, 68232, 68608, 68744, 69632, 70144, 70656, 70695, 70759, 71223, 71287, 71680, 71816, 72797, 73293, 73728, 73792, 74240, 74282, 74304, 74402, 74752, 74816, 74855, 75383, 75776, 75818, 75840, 75912, 75976, 76330, 77354, 77824, 77888, 77927, 78455, 78951, 78967, 79443, 79463, 79479, 79699, 80426, 80999, 81135, 81527, 81663, 81779, 81920, 81936, 81956, 82212, 82432, 82448, 82944, 83472, 83511, 83575, 83968, 84104, 84228, 84496, 84632, 85085, 86016, 86544, 86583, 86647, 87095, 87133, 87159, 87253, 87607, 87671, 88157, 89181, 89655, 89693, 89719, 89791, 89855, 90112, 90176, 90640, 90704, 90743, 91255, 91767, 92218, 92714, 93815, 93951, 94327, 94839, 95335, 95351, 95799, 95863, 95991, 95999, 96119, 96887, 97023, 97309, 97373, 97399, 97535, 97879, 97911, 98047, 98135, 98304, 98432, 98816, 98944, 99328, 99456, 100352, 100360, 100480, 100488, 102400, 102528, 106496, 106560, 106624, 106688, 109098, 109226, 111719, 111847, 112247, 112375, 114688, 114816, 115216, 115344, 120375, 120439, 120503, 120567, 121949, 122077, 124535, 124663, 127607, 127735, 128119, 128247, 128631, 128759, 130679, 130687, 130807, 130815, 131072, 131104, 131136, 131200, 131208, 131240, 131328, 131364, 131380, 131392, 131456, 131464, 131584, 131594, 131600, 131616, 131658, 131752, 131840, 131856, 131876, 131892, 132096, 132128, 132264, 132352, 132388, 132608, 132864, 132916, 133120, 133152, 133216, 133256, 133280, 133288, 133376, 133408, 133412, 133512, 133548, 133632, 133664, 133674, 133680, 133738, 133768, 133888, 133930, 133940, 133994, 134024, 134076, 134144, 134176, 134280, 134400, 134536, 134688, 135168, 135200, 135336, 135424, 135460, 135680, 135936, 135988, 136192, 136448, 137216, 137248, 137352, 137472, 137608, 137760, 138272, 139264, 139274, 139296, 139328, 139360, 139432, 139496, 139520, 139556, 139584, 139620, 139776, 139786, 139818, 139840, 139938, 140032, 140074, 140084, 140096, 140148, 140194, 140288, 140352, 140544, 140608, 140810, 141312, 141344, 141354, 141376, 141408, 141448, 141512, 141568, 141598, 141610, 141632, 141704, 141768, 141834, 141856, 141866, 141920, 141954, 142094, 142122, 142368, 142432, 142890, 143146, 143360, 143424, 143616, 143680, 143882, 145235, 145440, 145504, 145962, 146218, 147456, 147472, 147488, 147492, 147624, 147712, 147728, 147748, 147812, 147876, 147884, 147968, 147984, 148016, 148152, 148224, 148240, 148260, 148276, 148480, 148736, 148772, 149008, 149264, 149284, 149504, 149508, 149536, 149552, 149640, 149760, 149764, 149796, 149896, 149932, 150032, 150048, 150064, 150168, 150286, 150288, 150308, 150350, 150424, 150444, 150560, 150820, 150956, 151088, 151552, 151808, 151844, 152080, 152336, 152356, 152868, 153632, 153892, 154028, 154160, 155648, 155674, 155712, 155904, 155940, 155968, 156004, 156170, 156176, 156240, 156430, 156432, 156452, 156496, 156516, 156550, 156964, 157028, 157728, 157754, 157792, 157966, 157988, 158010, 158052, 158124, 158188, 158250, 158256, 158320, 158478, 158506, 159502, 160036, 160100, 161399, 161655, 162574, 163415, 163840, 163872, 163880, 163968, 164000, 164008, 164096, 164132, 164224, 164260, 164352, 164480, 164608, 164660, 164736, 164788, 164864, 164992, 165120, 165248, 165888, 165896, 165920, 166016, 166024, 166048, 166144, 166152, 166272, 166280, 166432, 166560, 166944, 167072, 167936, 168064, 168192, 168320, 170016, 170144, 172032, 172096, 172160, 172224, 172288, 172352, 172416, 172480, 172554, 172682, 174112, 174176, 174240, 174304, 174634, 174762, 174890, 175018, 180224, 180352, 180480, 180516, 180608, 180644, 180752, 180880, 181008, 181028, 181136, 181156, 181540, 181668, 182304, 182432, 182564, 182572, 182692, 182700, 182832, 182960, 184612, 184740, 188708, 188772, 188836, 188900, 191246, 191374, 196608, 196640, 196776, 196864, 196900, 197120, 197376, 197428, 197632, 197888, 198656, 198688, 198792, 198912, 199048, 199200, 199712, 200704, 200960, 202515, 202579, 202784, 204153, 204800, 204864, 205056, 205120, 205322, 206675, 206880, 206944, 207402, 207658, 209747, 210023, 210259, 210279, 210551, 210771, 210807, 212039, 212567, 212819, 212955, 212992, 213248, 213284, 213520, 213776, 213796, 214308, 215072, 215332, 215468, 215600, 217380, 218237, 218679, 218743, 218935, 218999, 220253, 220509, 220695, 220759, 221476, 221540, 222839, 223095, 224014, 224855, 225911, 226167, 226423, 226627, 226679, 226903, 226935, 227039, 227155, 227191, 227927, 228439, 228951, 228983, 229119, 229239, 229375, 229376, 229504, 229632, 229760, 231456, 231584, 243539, 243667, 246052, 246180, 259703, 259831, 259959, 260087, 261719, 261847], [16, 32, 36, 64, 128, 136, 168, 256, 288, 292, 424, 512, 528, 554, 564, 576, 618, 640, 648, 674, 738, 768, 820, 1024, 1088, 1152, 1160, 1280, 1536, 1552, 2048, 2056, 2080, 2090, 2112, 2154, 2176, 2184, 2248, 2304, 2308, 2336, 2440, 2560, 2576, 2592, 2602, 2666, 2696, 2712, 2836, 2848, 3072, 3104, 3208, 3360, 3584, 3626, 3690, 3720, 4096, 4160, 4224, 4232, 4352, 4608, 4624, 5120, 5632, 6144, 6176, 6280, 6432, 6656, 6698, 6762, 6792, 7168, 7304, 8192, 8234, 8256, 8320, 8328, 8354, 8384, 8392, 8448, 8512, 8704, 8714, 8720, 8746, 8768, 8784, 8866, 8970, 9216, 9280, 9728, 9770, 9792, 9890, 10240, 10272, 10282, 10298, 10304, 10336, 10376, 10440, 10528, 10592, 10752, 10794, 10816, 10858, 10888, 10914, 10922, 10952, 11050, 11264, 11306, 11328, 11400, 11464, 11818, 12288, 12352, 12800, 12842, 12864, 12962, 13312, 13376, 14336, 14378, 14400, 14472, 14536, 14890, 15914, 16384, 16400, 16420, 16448, 16512, 16520, 16640, 16644, 16676, 16780, 16896, 16912, 16932, 16976, 17040, 17048, 17168, 17188, 17408, 17424, 17444, 17700, 17920, 17936, 18432, 18448, 18464, 18468, 18490, 18554, 18568, 18584, 18604, 18692, 18720, 18724, 18860, 18944, 18960, 18986, 18992, 19050, 19080, 19096, 19204, 19248, 19456, 19592, 19716, 19984, 20120, 20480, 20496, 20516, 20772, 20992, 21008, 21504, 22032, 22528, 22664, 22788, 23056, 23192, 24576, 24592, 24612, 24634, 24640, 24656, 24676, 24754, 24868, 24932, 25088, 25104, 25130, 25152, 25168, 25250, 25390, 25600, 25664, 26128, 26192, 26624, 26666, 26682, 26688, 26760, 26824, 26884, 26948, 27150, 27152, 27178, 27194, 27216, 27288, 27352, 27406, 27706, 28202, 28672, 28736, 29200, 29264, 30327, 30778, 31274, 32768, 32776, 32832, 32896, 32904, 32960, 33024, 33152, 33280, 33296, 33408, 33424, 33792, 33920, 34304, 34432, 34816, 34824, 34848, 34944, 34952, 34976, 35104, 35232, 35328, 35336, 35370, 35434, 35456, 35464, 35498, 35562, 35840, 35848, 35968, 35976, 36864, 36992, 37376, 37504, 37888, 38016, 38912, 38920, 39040, 39048, 40960, 41024, 41088, 41152, 41472, 41506, 41514, 41536, 41600, 41634, 41642, 41664, 41984, 42048, 42112, 42176, 43008, 43016, 43050, 43072, 43080, 43136, 43144, 43178, 43200, 43208, 43562, 43690, 44586, 44714, 45056, 45120, 45184, 45248, 47658, 47786, 49152, 49168, 49188, 49280, 49296, 49316, 49444, 49572, 49664, 49680, 49792, 49808, 50176, 50304, 50704, 50832, 51200, 51208, 51328, 51336, 51460, 51588, 51728, 51736, 51856, 51864, 53248, 53376, 53776, 53904, 57344, 57408, 57472, 57536, 57872, 57936, 58000, 58064, 59450, 59578, 59946, 60074, 65536, 65600, 65664, 65672, 65792, 66048, 66064, 66560, 67072, 67584, 67616, 67720, 67872, 68096, 68138, 68202, 68232, 68608, 68744, 69632, 70144, 70656, 71680, 71816, 73728, 73792, 74240, 74282, 74304, 74402, 74752, 74816, 75776, 75818, 75840, 75912, 75976, 76330, 77354, 77824, 77888, 78951, 79479, 80426, 81920, 81936, 81956, 82212, 82432, 82448, 82944, 83472, 83968, 84104, 84228, 84496, 84632, 86016, 86544, 87607, 87671, 89181, 90112, 90176, 90640, 90704, 91767, 92218, 92714, 94839, 95351, 95863, 97911, 98047, 98304, 98432, 98816, 98944, 99328, 99456, 100352, 100360, 100480, 100488, 102400, 102528, 106496, 106560, 106624, 106688, 109098, 109226, 114688, 114816, 115216, 115344, 128631, 128759, 131072, 131104, 131136, 131200, 131208, 131240, 131328, 131364, 131380, 131392, 131456, 131464, 131584, 131594, 131600, 131616, 131658, 131752, 131840, 131856, 131876, 131892, 132096, 132128, 132264, 132352, 132388, 132608, 132864, 132916, 133120, 133152, 133216, 133256, 133280, 133288, 133376, 133408, 133412, 133512, 133548, 133632, 133664, 133674, 133680, 133738, 133768, 133888, 133930, 133940, 133994, 134024, 134076, 134144, 134176, 134280, 134400, 134536, 134688, 135168, 135200, 135336, 135424, 135460, 135680, 135936, 135988, 136192, 136448, 137216, 137248, 137352, 137472, 137608, 137760, 138272, 139264, 139274, 139296, 139328, 139360, 139432, 139496, 139520, 139556, 139584, 139620, 139776, 139786, 139818, 139840, 139938, 140032, 140074, 140084, 140096, 140148, 140194, 140288, 140352, 140544, 140608, 140810, 141312, 141344, 141354, 141376, 141408, 141448, 141512, 141568, 141598, 141610, 141632, 141704, 141768, 141834, 141856, 141866, 141920, 141954, 142094, 142122, 142368, 142432, 142890, 143146, 143360, 143424, 143616, 143680, 143882, 145440, 145504, 145962, 146218, 147456, 147472, 147488, 147492, 147624, 147712, 147728, 147748, 147812, 147876, 147884, 147968, 147984, 148016, 148152, 148224, 148240, 148260, 148276, 148480, 148736, 148772, 149008, 149264, 149284, 149504, 149508, 149536, 149552, 149640, 149760, 149764, 149796, 149896, 149932, 150032, 150048, 150064, 150168, 150286, 150288, 150308, 150350, 150424, 150444, 150560, 150820, 150956, 151088, 151552, 151808, 151844, 152080, 152336, 152356, 152868, 153632, 153892, 154028, 154160, 155648, 155674, 155712, 155904, 155940, 155968, 156004, 156170, 156176, 156240, 156430, 156432, 156452, 156496, 156516, 156550, 156964, 157028, 157728, 157754, 157792, 157966, 157988, 158010, 158052, 158124, 158188, 158250, 158256, 158320, 158478, 158506, 159502, 160036, 160100, 162574, 163840, 163872, 163880, 163968, 164000, 164008, 164096, 164132, 164224, 164260, 164352, 164480, 164608, 164660, 164736, 164788, 164864, 164992, 165120, 165248, 165888, 165896, 165920, 166016, 166024, 166048, 166144, 166152, 166272, 166280, 166432, 166560, 166944, 167072, 167936, 168064, 168192, 168320, 170016, 170144, 172032, 172096, 172160, 172224, 172288, 172352, 172416, 172480, 172554, 172682, 174112, 174176, 174240, 174304, 174634, 174762, 174890, 175018, 180224, 180352, 180480, 180516, 180608, 180644, 180752, 180880, 181008, 181028, 181136, 181156, 181540, 181668, 182304, 182432, 182564, 182572, 182692, 182700, 182832, 182960, 184612, 184740, 188708, 188772, 188836, 188900, 191246, 191374, 196608, 196640, 196776, 196864, 196900, 197120, 197376, 197428, 197632, 197888, 198656, 198688, 198792, 198912, 199048, 199200, 199712, 200704, 200960, 202784, 204800, 204864, 205056, 205120, 205322, 206880, 206944, 207402, 207658, 210771, 212992, 213248, 213284, 213520, 213776, 213796, 214308, 215072, 215332, 215468, 215600, 217380, 221476, 221540, 224014, 226935, 227191, 228951, 229376, 229504, 229632, 229760, 231456, 231584, 246052, 246180, 262144, 262208, 262272, 262280, 262400, 262656, 262672, 263168, 263680, 264192, 264224, 264328, 264480, 264704, 264746, 264810, 264840, 265216, 265352, 266240, 266752, 267264, 268288, 268424, 270336, 270400, 270848, 270890, 270912, 271010, 271360, 271424, 272384, 272426, 272448, 272520, 272584, 272938, 273962, 274432, 274496, 275559, 276087, 277034, 278528, 278544, 278564, 278820, 279040, 279056, 279552, 280080, 280576, 280712, 280836, 281104, 281240, 282624, 283152, 284215, 284279, 285789, 286720, 286784, 287248, 287312, 288375, 288826, 289322, 291447, 291959, 292471, 294519, 294655, 294912, 295040, 295424, 295552, 295936, 296064, 296960, 296968, 297088, 297096, 299008, 299136, 303104, 303168, 303232, 303296, 305706, 305834, 311296, 311424, 311824, 311952, 325239, 325367, 327680, 328192, 328704, 329728, 329864, 331776, 332839, 332903, 333367, 333431, 334941, 335437, 335872, 335936, 336999, 337527, 338474, 340071, 340599, 341095, 341111, 341587, 341607, 341623, 341843, 343143, 343279, 343671, 343807, 343923, 344064, 344592, 345655, 345719, 347229, 348727, 348791, 349239, 349277, 349303, 349397, 349751, 349815, 350301, 351325, 351799, 351837, 351863, 351935, 351999, 352887, 353399, 353911, 355959, 356095, 356471, 356983, 357479, 357495, 357943, 358007, 358135, 358143, 358263, 359031, 359167, 359453, 359517, 359543, 359679, 360023, 360055, 360191, 360279, 360448, 360576, 373863, 373991, 374391, 374519, 382519, 382583, 382647, 382711, 384093, 384221, 386679, 386807, 389751, 389879, 390263, 390391, 390775, 390903, 392823, 392831, 392951, 392959, 393216, 393248, 393384, 393472, 393508, 393728, 393984, 394036, 394240, 394496, 395264, 395296, 395400, 395520, 395656, 395808, 396320, 397312, 397568, 399392, 401408, 401472, 401664, 401728, 401930, 403488, 403552, 404010, 404266, 407379, 409600, 409856, 409892, 410128, 410384, 410404, 410916, 411680, 411940, 412076, 412208, 413988, 418084, 418148, 420622, 423543, 423799, 425559, 425984, 426112, 426240, 426368, 428064, 428192, 442660, 442788, 458752, 459008, 460832, 464659, 464723, 466297, 468819, 471891, 472167, 472403, 472423, 472695, 472915, 472951, 474183, 474711, 474963, 475099, 475428, 480381, 480823, 480887, 481079, 481143, 482397, 482653, 482839, 482903, 484983, 485239, 486999, 488055, 488311, 488567, 488771, 488823, 489047, 489079, 489183, 489299, 489335, 490071, 490583, 491095, 491127, 491263, 491383, 491519, 505683, 505811, 521847, 521975, 522103, 522231, 523863, 523991]]

def solve():
    (n, m) = read_int_tuple()
    if n == 15 or n >= 20:
        for _ in range(m):
            input()
        print(n)
        print(*range(1, n + 1))
        return
    if n < 5:
        print(-1)
        return
    toget = [0] * n
    for _ in range(m):
        (u, v) = read_ints_minus_one()
        toget[u] |= 1 << v
    for mask in candis[n]:
        if all((toget[i] | mask == mask for i in range(n) if mask >> i & 1)):
            print(bin(mask).count('1'))
            print(*[i + 1 for i in range(n) if mask >> i & 1])
            return
    print(-1)

def main():
    if 'AW' in os.environ.get('COMPUTERNAME', ''):
        test_no = 1
        f = open(os.path.dirname(__file__) + f'\\in{test_no}.txt', 'r')
        global input
        input = lambda : f.readline().rstrip('\r\n')
    T = 1
    T = read_int()
    for t in range(T):
        solve()
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_ints_minus_one():
    return [int(x) - 1 for x in input().split()]

def read_int_tuple():
    return map(int, input().split())

def read_encode_str(d=97):
    return [ord(x) - d for x in input()]

def read_graph(n: int, m: int, d=1):
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - d].append(v - d)
        g[v - d].append(u - d)
    return g

def read_grid(m: int):
    return [input() for _ in range(m)]

def read_int():
    return int(input())
read_str = input
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import itertools

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    a = [readList() for _ in range(m)]
    if n >= 20:
        print(n)
        print(' '.join([str(i + 1) for i in range(n)]))
    else:
        S = (1 << n) - 1
        for cnt in range(1, n // 5 + 1):
            for v in nums[cnt]:
                if v > S:
                    break
                flag = 0
                for (x, y) in a:
                    flag |= p[x - 1] & idx[v] and (not p[y - 1] & idx[v])
                    if flag:
                        break
                if not flag:
                    ans = [i + 1 for i in range(n) if 1 << i & idx[v]]
                    print(len(ans))
                    print(*ans)
                    return
        print(-1)
    return
p = [1 << i for i in range(20)]
nums = [[], [], [], []]
for i in range(20):
    nums[1].append(p[i])
    for j in range(i + 1, 20):
        nums[2].append(p[i] + p[j])
        for k in range(j + 1, 20):
            nums[3].append(p[i] + p[j] + p[k])
idx = [0] * (1 << 20)
for each in nums:
    for v in each:
        curr = [0] * 21
        on = [0] + [1 if p[u] & v else 0 for u in range(20)]
        for j in range(1, 21):
            if curr[j] == on[j]:
                continue
            idx[v] += 1 << j - 1
            for k in range(j, 21, j):
                curr[k] ^= 1
nums[1].sort()
nums[2].sort()
nums[3].sort()
for _ in range(int(input())):
    solve()