Description：

给出一个图和一个该图的哈密顿回路，问该图是否为平面图。

$1\le T \le 100$ $3\le N \le 200$ $1\le M \le 10000$

Solution：

先用平面图的性质 边数 $\le$ 点数 $\times3-6$ 将边数缩小到 $O(n)$ 级别，对于不在哈密顿回路上的每条边，都有连在环内和连在环外两种选择，但是有的边和边同时连在环内和环外时会交叉，于是这就是一个 $2-SAT$ 模型，两个交叉的边不能同时选，判交叉用顶点顺序。

多组数据一定要读完！！！

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 210000

int x[200000],y[200000];

#define MAXP (MAXN * 3 * 2)

struct edge

{

    int to,nxt;

}e[200000];

int edgenum = 0;

int lin[MAXP] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum; 

    return;

}

int dfn[MAXP],low[MAXP],tot = 0;

bool v[MAXP];

stack<int> s;

int scc = 0,ins[MAXP];

void tarjan(int k)

{

    dfn[k] = low[k] = ++tot;

    v[k] = true;s.push(k);

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(dfn[e[i].to] == 0)

        {

            tarjan(e[i].to);

            low[k] = min(low[k],low[e[i].to]);

        }

        else if(v[e[i].to])

        {

            low[k] = min(low[k],dfn[e[i].to]);

        }

    }

    if(low[k] == dfn[k])

    {

        int t;

        ++scc;

        do

        {

            t = s.top();s.pop();

            v[t] = false;

            ins[t] = scc;

        }while(t != k);

    }

    return;

}

int rank[MAXN];

void work()

{

    memset(e,0,sizeof(e));

    memset(x,0,sizeof(x));

    memset(y,0,sizeof(y));

    memset(lin,0,sizeof(lin));

    edgenum = 0;

    memset(rank,0,sizeof(rank));

    memset(dfn,0,sizeof(dfn));

    memset(low,0,sizeof(low));

    tot = 0;

    scc = 0;

    memset(ins,0,sizeof(ins));

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

    while(!s.empty())s.pop();

    cin >> n >> m;

    for(int i = 1;i <= m;++i)

    {

        cin >> x[i] >> y[i];

    }

    int kkk;

    for(int i = 1;i <= n;++i)

    {

        cin >> kkk;

        rank[kkk] = i;

    }

    if(m > 3 * n - 6)

    {

        puts("NO");

        return;

    }

    for(int i = 1;i <= m;++i)

    {

        if(rank[x[i]] > rank[y[i]])swap(x[i],y[i]);

    }

    for(int i = 1;i <= m;++i)

    {

        for(int j = 1;j <= m;++j)

        {

            if(i == j)continue;

            if(rank[x[i]] < rank[x[j]] && rank[x[j]] < rank[y[i]] && rank[y[i]] < rank[y[j]])

            {

                add((i - 1) * 2 + 1,(j - 1) * 2 + 2);

                add((i - 1) * 2 + 2,(j - 1) * 2 + 1);

            }

        }

    }

    for(int i = 1;i <= 2 * m;++i)

    {

        if(dfn[i] == 0)

        {

            tarjan(i);

        }

    }

    bool found = false;

    for(int i = 1;i <= m;++i)

    {

        if(ins[(i - 1) * 2 + 1] == ins[(i - 1) * 2 + 2])

        {

            found = true;

            break;

        }

    }

    if(found)puts("NO");

    else puts("YES");

    return;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)work();

    return 0;

}