Description

Welcome to the Annual Byteland Shooting Contest. Each competitor will shoot to a target which is a rectangular grid. The target consists of r*c squares located in r rows and c columns. The squares are coloured white or black. There are exactly two white squares and r-2 black squares in each column. Rows are consecutively labelled 1,..,r from top to bottom and columns are labelled 1,..,c from left to right. The shooter has c shots. 

A volley of c shots is correct if exactly one white square is hit in each column and there is no row without white square being hit. Help the shooter to find a correct volley of hits if such a volley exists. 
Example 
Consider the following target: 

Volley of hits at white squares in rows 2, 3, 1, 4 in consecutive columns 1, 2, 3, 4 is correct. 
Write a program that: verifies whether any correct volley of hits exists and if so, finds one of them.

Input

Output

Sample Input

2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3

Sample Output

2 3 1 4
NO
//二分匹配，列作为第一点集，行作为第二点集，白点作为行和列的边建图，然后匈牙利算法，注意列大于行时的情况
//之前没考虑到列大于行时的情况，导致一直wa。列大于行时，匈牙利结束后，没有被匹配的列，随便从此列找个白点就行
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int N = 1010;

int match[N];
bool use[N];
bool s[N][N];
int r, c;

bool dfs(int v)
{
    for(int i = 1; i <= r; i++)
    {
        if(s[v][i] == true && use[i] == false)
        {
            use[i] = true;
            if(match[i] == -1 || dfs(match[i]))
            {
                match[i] = v;
                return true;
            }
        }
    }

    return false;
}

int hungary()
{
    int res = 0;
    memset(match, -1, sizeof match);
    for(int i = 1; i <= c; i++)
    {
        memset(use, 0, sizeof use);
        if(dfs(i)) res++;
    }

    return res;
}

int main()
{
    int t, a, b;

    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &r, &c);

        memset(s, 0, sizeof s);
        for(int i = 1; i <= c; i++)
        {
            scanf("%d%d", &a, &b);
            s[i][a] = true;
            s[i][b] = true;
        }

        if(hungary() == r) //相等说明每行都被列所匹配，即每行都有白点
        {

            for(int i = 1; i <= c; i++)
            {
                int res = -1;
                for(int j = 1; j <= r; j++)
                    if(match[j] == i)
                    {
                        res = j;
                        break;
                    }

                if(res == -1)
                {
                    for(int j = 1; j <= r; j++)
                        if(s[i][j] != 0)
                        {
                            res = j;
                            break;
                        }
                }

                if(i == 1) printf("%d", res);
                else printf(" %d", res);
            }
        }
        else printf("NO");
        printf("\n");
    }

    return 0;
}