#include <iostream>
using namespace std;
//Using BST to find distinct elements in an array
// We store the array elements in BST and then count the number of nodes in BST as these will be the only distinct elements
// The time complexity to insert all array elements in BST is O(nlogn) on avg and O(n_square) in worst case
// The time complexity to count nodes in bst is O(logn) for a balanced tree and O(n_square) if sorted array.
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class BST {
private:
TreeNode* root;
// Recursive function to insert a value into the BST
TreeNode* insert(TreeNode* node, int value) {
if (node == nullptr) {
return new TreeNode(value);
}
if (value < node->data) {
node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
}
return node;
}
// Recursive function to count the number of nodes in the BST
int countNodes(TreeNode* node) {
if (node == nullptr) {
return 0;
}
return 1 + countNodes(node->left) + countNodes(node->right);
}
public:
BST() : root(nullptr) {}
void insert(int value) {
root = insert(root, value);
}
int countDistinct() {
return countNodes(root);
}
};
// Function to classify the array based on the number of distinct elements
string classifyArray(int N, int X, int A[]) {
BST bst;
for (int i = 0; i < N; ++i) {
bst.insert(A[i]);
}
int distinctCount = bst.countDistinct();
// Compareing the count of distinct elements with the expected count and classifying the array accordingly
if (distinctCount == X)
return "Good";
else if (distinctCount < X)
return "Bad";
else
return "Average";
}
int main() {
int T;
cin >> T;
for (int t = 0; t < T; ++t) {
int N, X;
cin >> N >> X;
int A[N];
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
cout << classifyArray(N, X, A) << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vVXNpbmcgQlNUIHRvIGZpbmQgZGlzdGluY3QgZWxlbWVudHMgaW4gYW4gYXJyYXkKLy8gV2Ugc3RvcmUgdGhlIGFycmF5IGVsZW1lbnRzIGluIEJTVCBhbmQgdGhlbiBjb3VudCB0aGUgbnVtYmVyIG9mIG5vZGVzIGluIEJTVCBhcyB0aGVzZSB3aWxsIGJlIHRoZSBvbmx5IGRpc3RpbmN0IGVsZW1lbnRzCi8vIFRoZSB0aW1lIGNvbXBsZXhpdHkgdG8gaW5zZXJ0IGFsbCBhcnJheSBlbGVtZW50cyBpbiBCU1QgaXMgTyhubG9nbikgb24gYXZnIGFuZCBPKG5fc3F1YXJlKSBpbiB3b3JzdCBjYXNlCi8vIFRoZSB0aW1lIGNvbXBsZXhpdHkgdG8gY291bnQgbm9kZXMgaW4gYnN0IGlzIE8obG9nbikgZm9yIGEgYmFsYW5jZWQgdHJlZSBhbmQgTyhuX3NxdWFyZSkgaWYgc29ydGVkIGFycmF5LgpjbGFzcyBUcmVlTm9kZSB7CnB1YmxpYzoKICAgIGludCBkYXRhOwogICAgVHJlZU5vZGUqIGxlZnQ7CiAgICBUcmVlTm9kZSogcmlnaHQ7CgogICAgVHJlZU5vZGUoaW50IHZhbCkgOiBkYXRhKHZhbCksIGxlZnQobnVsbHB0ciksIHJpZ2h0KG51bGxwdHIpIHt9Cn07CgpjbGFzcyBCU1Qgewpwcml2YXRlOgogICAgVHJlZU5vZGUqIHJvb3Q7CiAgICAvLyBSZWN1cnNpdmUgZnVuY3Rpb24gdG8gaW5zZXJ0IGEgdmFsdWUgaW50byB0aGUgQlNUCiAgICBUcmVlTm9kZSogaW5zZXJ0KFRyZWVOb2RlKiBub2RlLCBpbnQgdmFsdWUpIHsKICAgICAgICBpZiAobm9kZSA9PSBudWxscHRyKSB7CiAgICAgICAgICAgIHJldHVybiBuZXcgVHJlZU5vZGUodmFsdWUpOwogICAgICAgIH0KCiAgICAgICAgaWYgKHZhbHVlIDwgbm9kZS0+ZGF0YSkgewogICAgICAgICAgICBub2RlLT5sZWZ0ID0gaW5zZXJ0KG5vZGUtPmxlZnQsIHZhbHVlKTsKICAgICAgICB9IGVsc2UgaWYgKHZhbHVlID4gbm9kZS0+ZGF0YSkgewogICAgICAgICAgICBub2RlLT5yaWdodCA9IGluc2VydChub2RlLT5yaWdodCwgdmFsdWUpOwogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIG5vZGU7CiAgICB9CgogICAgLy8gUmVjdXJzaXZlIGZ1bmN0aW9uIHRvIGNvdW50IHRoZSBudW1iZXIgb2Ygbm9kZXMgaW4gdGhlIEJTVAogICAgaW50IGNvdW50Tm9kZXMoVHJlZU5vZGUqIG5vZGUpIHsKICAgICAgICBpZiAobm9kZSA9PSBudWxscHRyKSB7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0KICAgICAgICByZXR1cm4gMSArIGNvdW50Tm9kZXMobm9kZS0+bGVmdCkgKyBjb3VudE5vZGVzKG5vZGUtPnJpZ2h0KTsKICAgIH0KCnB1YmxpYzoKICAgIEJTVCgpIDogcm9vdChudWxscHRyKSB7fQoKICAgIHZvaWQgaW5zZXJ0KGludCB2YWx1ZSkgewogICAgICAgIHJvb3QgPSBpbnNlcnQocm9vdCwgdmFsdWUpOwogICAgfQoKICAgIGludCBjb3VudERpc3RpbmN0KCkgewogICAgICAgIHJldHVybiBjb3VudE5vZGVzKHJvb3QpOwogICAgfQp9OwoKLy8gRnVuY3Rpb24gdG8gY2xhc3NpZnkgdGhlIGFycmF5IGJhc2VkIG9uIHRoZSBudW1iZXIgb2YgZGlzdGluY3QgZWxlbWVudHMKc3RyaW5nIGNsYXNzaWZ5QXJyYXkoaW50IE4sIGludCBYLCBpbnQgQVtdKSB7CiAgICBCU1QgYnN0OwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTjsgKytpKSB7CiAgICAgICAgYnN0Lmluc2VydChBW2ldKTsKICAgIH0KCiAgICBpbnQgZGlzdGluY3RDb3VudCA9IGJzdC5jb3VudERpc3RpbmN0KCk7CiAgICAvLyBDb21wYXJlaW5nIHRoZSBjb3VudCBvZiBkaXN0aW5jdCBlbGVtZW50cyB3aXRoIHRoZSBleHBlY3RlZCBjb3VudCBhbmQgY2xhc3NpZnlpbmcgdGhlIGFycmF5IGFjY29yZGluZ2x5CiAgICBpZiAoZGlzdGluY3RDb3VudCA9PSBYKQogICAgICAgIHJldHVybiAiR29vZCI7CiAgICBlbHNlIGlmIChkaXN0aW5jdENvdW50IDwgWCkKICAgICAgICByZXR1cm4gIkJhZCI7CiAgICBlbHNlCiAgICAgICAgcmV0dXJuICJBdmVyYWdlIjsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgVDsKICAgIGNpbiA+PiBUOwoKICAgIGZvciAoaW50IHQgPSAwOyB0IDwgVDsgKyt0KSB7CiAgICAgICAgaW50IE4sIFg7CiAgICAgICAgY2luID4+IE4gPj4gWDsKCiAgICAgICAgaW50IEFbTl07CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyArK2kpIHsKICAgICAgICAgICAgY2luID4+IEFbaV07CiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8IGNsYXNzaWZ5QXJyYXkoTiwgWCwgQSkgPDwgZW5kbDsKICAgIH0KCiAgICByZXR1cm4gMDsKfQ==