[TIOJ 1690][NPSC 2009 決賽]H.補習班的報名熱

這題可以轉換成精確覆蓋問題

甚麼是精確覆蓋問題？
$_{註1}$舉個例子，給你一堆$<2^{n}$的數字，叫你選出幾個，使得他們AND (&) 起來是0，OR (|) 起來是$2^{n}-1$
請用二近位的角度去想

這題轉換後會變成一個$N$行$M$列，每列有2個1 (每條邊的兩端點) 的矩陣

第一個範測轉換後變成以下矩陣：
1100
0110
0011
1001

第二個範測轉換後變成以下矩陣：
1100
0110
0011

如果還沒看出我們要幹嘛，請再看一次$_{註1}$

這種問題我想直接dfs試誤枚舉耶
每挑一列就把和那列的1有衝突的每一列都刪掉，失敗了再慢慢把每一列復原，挑另一列繼續做
當剛好全部覆蓋時就找到答案了

怎麼優化？
對於同一行，都剛好只會有一個1被選到，因此只要選這些1出現的那幾列就好了，然後就可以直接return，不用找另外一行
每一次做抉擇時，我們可以直接選擇1最少的那一行，這樣可以最小化分枝 (嘗試次數最少)

可是刪除一列需要$O(M*N)$的時間耶
用鏈表也需要$O(N)$......
那些0好煩Orz

那鏈表裡面不要把0存起來就好啦
這樣刪除一列只需要涉及2個1，形同$O(1)$刪列！

這就是舞蹈鏈 ($Dancing\ Links$) 的思想
如果自己實踐出了問題，可以看這篇確認想法
或者這篇確認操作過程
有些觀念可能遭誤解，因此建議和這裡比對一下

時間複雜度：無法確定 (上界應該是$O(M^{N})$，不過實際執行時間幾乎都是遠小於這個數字，像我這份code跑$20ms$超快www)

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#define debug(x,...) //printf(x,##__VA_ARGS__)
using namespace std;
struct Edge
{
    int a,b;
    Edge(){}
    Edge(const int _a,const int _b):a(min(_a,_b)),b(max(_a,_b)){}
    bool operator<(const Edge &e)const{return a!=e.a?a<e.a:b<e.b;}
};
vector<Edge>EDGE;
struct Node
{
    Node *left,*right,*up,*down;
    const int r,c;
    Node(const int _r,const int _c):left(this),right(this),up(this),down(this),r(_r),c(_c){}
}*COL[1000],*ROW[10000],*ORIGIN=new Node(-1,-1);
void InsertH(Node *l,Node *o,Node *r){l->right=o,o->right=r,r->left=o,o->left=l;}
void InsertV(Node *u,Node *o,Node *d){u->down=o,o->down=d,d->up=o,o->up=u;}
int CNT[1000];
void AddNode(const int r,const int c)
{
    Node *o=new Node(r,c);
    InsertH(ROW[r]->left,o,ROW[r]),InsertV(COL[c]->up,o,COL[c]);
    CNT[c]++;
}
int N,M;
bool IsConnectedV(Node *o)
{
    assert((o->up->down==o)==(o->down->up==o));
    return (o->up->down==o);
}
void DisconnectV(Node *o){debug("unlinkV(%d,%d)\n",o->r,o->c);assert(IsConnectedV(o));o->up->down=o->down,o->down->up=o->up;CNT[o->c]--;assert(!IsConnectedV(o));}
void ConnectV(Node *o){debug("  linkV(%d,%d)\n",o->r,o->c);assert(!IsConnectedV(o));o->up->down=o->down->up=o;CNT[o->c]++;assert(IsConnectedV(o));}
void RemoveRow(const int r)
{
    debug("remove  row%d\n",r);
    Node *row=ROW[r],*cur=row;
    do{DisconnectV(cur),cur=cur->right;}while(cur!=row);
}
void RestoreRow(const int r)
{
    debug("restore row%d\n",r);
    Node *row=ROW[r],*cur=row;
    do{ConnectV(cur),cur=cur->right;}while(cur!=row);
}
bool IsConnectedH(Node *o)
{
    assert((o->left->right==o)==(o->right->left==o));
    return (o->left->right==o);
}
void DisconnectH(Node *o){debug("unlinkH(%d,%d)\n",o->r,o->c);assert(IsConnectedH(o));o->left->right=o->right,o->right->left=o->left;assert(!IsConnectedH(o));}
void ConnectH(Node *o){debug("  linkH(%d,%d)\n",o->r,o->c);assert(!IsConnectedH(o));o->left->right=o->right->left=o;assert(IsConnectedH(o));}
void RemoveCol(const int c){debug("remove  col%d\n",c);DisconnectH(COL[c]);}//為避免資訊遺失，只移除表頭 
void RestoreCol(const int c){debug("restore col%d\n",c);ConnectH(COL[c]);}//為避免資訊遺失，只移除表頭
void SelectRow(const int r)
{
    debug("  select %d\n",r);
    Node *row=ROW[r];
    assert(IsConnectedV(row));
    for(Node *cur1=row->right;cur1!=row;cur1=cur1->right)
    {
        assert(IsConnectedV(cur1));
        for(Node *cur2=cur1->down;cur2!=cur1;cur2=cur2->down)if(cur2->r!=-1)RemoveRow(cur2->r),ConnectV(cur2);//為避免資訊遺失，cur2要接回來 
    }
    for(Node *cur1=row->right;cur1!=row;cur1=cur1->right)RemoveCol(cur1->c);
    RemoveRow(r);
}
void UnselectRow(const int r)
{
    debug("unselect %d\n",r);
    RestoreRow(r);
    Node *row=ROW[r];
    assert(IsConnectedV(row));
    for(Node *cur1=row->left;cur1!=row;cur1=cur1->left)RestoreCol(cur1->c);
    for(Node *cur1=row->left;cur1!=row;cur1=cur1->left)//刪除時往右，反操作要往左 
    {
        assert(IsConnectedV(cur1));
        for(Node *cur2=cur1->up;cur2!=cur1;cur2=cur2->up)if(cur2->r!=-1)DisconnectV(cur2),RestoreRow(cur2->r);//反向操作，刪除時往下，反操作要往上  
    }
}
int Dance(vector<int>&now,vector<int>&ans)
{
    if(ORIGIN->right==ORIGIN)
    {
        if(ORIGIN->down==ORIGIN){ans=now;return 1;}
        else{return 2;}
    }
    Node *col=ORIGIN;
    for(Node *cur=ORIGIN->right;cur!=ORIGIN;cur=cur->right)
    {
        if(CNT[cur->c]==0)return 0;
        if(col==ORIGIN||CNT[cur->c]<CNT[col->c])col=cur;
    }
    assert(col!=ORIGIN);
    int solution_count=0;
    for(Node *row=col->down;row!=col&&solution_count<=1;row=row->down)
    {
        now.push_back(row->r);
        SelectRow(row->r);
        solution_count+=Dance(now,ans);
        UnselectRow(row->r);
        now.pop_back();
    }
    return solution_count;
}
int main()
{
//    freopen("in.txt","r",stdin);
    for(int i=0;i<1000;i++)COL[i]=NULL;
    for(int i=0;i<10000;i++)ROW[i]=NULL;
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d",&N,&M);
        for(int i=0;i<N;i++)if(COL[i])delete COL[i];
        for(int i=0;i<M;i++)if(ROW[i])delete ROW[i];
        delete ORIGIN;ORIGIN=new Node(-1,-1);
        for(int i=0;i<N;i++)COL[i]=new Node(-1,i),InsertH(ORIGIN->left,COL[i],ORIGIN),CNT[i]=0;
        for(int i=0;i<M;i++)ROW[i]=new Node(i,-1),InsertV(ORIGIN->up,ROW[i],ORIGIN);
        EDGE.clear();
        for(int i=0,a,b;i<M;i++)scanf("%d%d",&a,&b),EDGE.push_back(Edge(--a,--b));
        sort(EDGE.begin(),EDGE.end());
        for(int i=0;i<M;i++)
        {
            const Edge &e=EDGE[i];
            AddNode(i,e.a),AddNode(i,e.b);
        }
        vector<int>now,ans;
        const int result=Dance(now,ans);//全部主要計算都在這一行 
        //確認一下舞蹈鏈有沒有受損 
        for(int i=0;i<N;i++)assert(IsConnectedH(COL[i]));
        for(int i=0;i<M;i++)
        {
            assert(IsConnectedV(ROW[i]));
            int j=1;
            for(Node *cur=ROW[i]->right;cur!=ROW[i];cur=cur->right,j++)
            {
                assert(IsConnectedV(cur));
                if(j==1)assert(cur->c==EDGE[i].a);
                else if(j==2)assert(cur->c==EDGE[i].b);
                else assert(0);
            }
        }
        //損害確認通過 
        if(result==1)
        {
            puts("YES");
            sort(ans.begin(),ans.end());
            for(const int ei:ans)printf("%d %d\n",EDGE[ei].a+1,EDGE[ei].b+1);
        }
        else puts("NO");
    }
    return 0;
}