Field Trip

We heartily thank Clive Fraser for this problem!

Ann is a teacher who is organising a field trip for a group of children. The children have to work in pairs on the field trip so it is very important to ensure that each of the children in a pair have worked together successfully before. All of the children have at least one other child with whom they can work successfully. Ann has a list of all successful pairings (there are P of these) and must find a way of choosing pairs of children (from the N children going on the trip) so that each child is in a successful pair and no child is allocated to more than one pair.

Although the number N of children is even, Ann is not sure that it is possible to achieve the allocation using only the currently known successful pairs. If it is not possible to do this, Ann might have to take a risk by making one or more pairs that have no previous experience of working successfully together.

In this problem you will be given N, the number of children on the trip and P successful pairings. The children are numbered from 1 to N and each successful pairing consists of the numbers of the two children in that pairing. In the first of the 3 examples below, there are 8 children and 8 successful pairings. It is possible to allocate all 8 children using the successful pairings (7,5), (8,4), (1,2) and (6,3). You should be able to verify that, in the second example, all of the children can once again be allocated using the successful pairings. However, in the third example there is no combination of 9 successful pairings that results in all of the children being allocated.

The first line of the problem will be a single integer T denoting the number of test cases. Each test case will consist of two lines. The first of these will be a pair of integers separated by a space. These are N, the number of children and P, the number of pairs. The second line will contain 2P space-separated integers. The first two of these refer to the children in the first successful pair. The next two are the second pair, and so on. For each test case you must determine whether or not all of the children can all be allocated to pairs, using only the successful pairs provided. Answer 1 if such an allocation is possible and 0 if it is not. Give these answers, separated by spaces, as a single string.

Example:

input:
3
8 8
8 3 7 5 8 4 3 5 1 2 8 6 6 3 1 8
8 13
2 8 5 3 6 2 5 7 3 4 1 5 6 4 7 8 2 4 1 7 6 5 2 5 7 4
18 22
10 13 7 6 2 3 8 7 4 6 2 1 10 9 15 14 18 16 3 1 12 11 5 4 11 13 6 5 13 8 2 9 15 16 13 12 18 17 14 16 13 15 17 16

answer:
1 1 0