#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;

const int maxn = 100005;

int A, B, N, M;
int v[maxn];
vector<int> G[maxn];

int Find(int k)
{
    queue<int> Q1;
    queue<int> Q2;

    int i, len, sum1 = 1, sum2 = 0;

    Q1.push(k), v[k] = 1;

    while(Q1.size() || Q2.size())
    {
        if(Q1.size())
        {
            k = Q1.front();Q1.pop();
            len = G[k].size();
            for(i=0; i<len; i++)
            {
                int j = G[k][i];
                if(v[j] == 1)
                    return 0;
                if(v[j] == 0)
                {
                    v[j] = 2;
                    Q2.push(j);
                    sum2++;
                }
            }
            G[k].clear();
        }
        else
        {
            k = Q2.front();Q2.pop();
            len = G[k].size();

            for(i=0; i<len; i++)
            {
                int j = G[k][i];
                if(v[j] == 2)
                    return 0;
                if(v[j] == 0)
                {
                    v[j] = 1;
                    Q1.push(j);
                    sum1++;
                }
            }
            G[k].clear();
        }
    }

    A += max(sum1, sum2);
    B += min(sum1, sum2);

    return 1;
}

int main()
{
    int T;

    scanf("%d", &T);

    while(T--)
    {
        int i, x, y;

        scanf("%d%d", &N, &M);

        for(i=1; i<=N; i++)
            G[i].clear();

        memset(v, 0, sizeof(v));

        if(N < 2)
        {
            printf("Poor wyh\n");
            continue;
        }

        for(i=0; i<M; i++)
        {
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }

        A = B = 0;

        for(i=1; i<=N; i++)
        {
            if(G[i].size())
            {
                if(Find(i) == 0)
                    break;
            }
        }

        if(i <= N)
            printf("Poor wyh\n");
        else
        {
            for(i=1; i<=N; i++)
            {
                if(v[i] == 0)
                    A++;
            }

            if(A == N)
            {
                A --;
                B = 1;
            }
            printf("%d %d\n", A, B);
        }
    }

    return 0;
}
/*
10
3 3
1 2
1 3
2 3
3 2
1 2
1 3
*/