最小点覆盖：选出的一个点集 使得任意一条边都至少有一个端点属于该点集
最小点覆盖 = 最大边匹配数

最大独立集：在一个图中选出最多的点 使得选出的点内部之间没有边
等价于去掉最少的点 使剩下的点没有边 等价于去点最小点覆盖的数量
所以最大独立集 = 最大匹配数 - 最小点覆盖

最小路径点覆盖：在一个DAG中 求最少的路径能够包括所有的点 且每个点只属于一条路径 单独的点是一条长度为0的路径
最小路径点覆盖 = 最大独立集 = 原图点数 - 新二分图最大匹配数
证明：一开始每个点都是单独一个路径 当连接一条边时 相当于合并两条路径为一条 路径数 - 1 有m条匹配边 路径数就减少了m 剩余路径数位n - m
由于路径之间不能有公共点 所以边也不能有公共点 即为二分图的最大匹配
所以最小路径点覆盖 = 点数 - 最大匹配数

最小重复路径点覆盖  最小路径点覆盖的基础上 路径经过的点可以被另外一条路径经过
若u->p->v  和 x->p->y 则传递闭包直接x->y连边转化为最小路径点覆盖问题
最小重复路径点覆盖求传递闭包后 可以变为最小路径点覆盖 可以转化为点数 - 最大匹配数即可

对于无向图：(所有边都是连通的)

存在欧拉路径的充分必要条件：有两个或0个点度数为1 其余点度数均为2

存在欧拉回路(即起点和终点一致的欧拉路径)的充分必要条件: 所有点度数均为偶数

对于有向图(所有边都联通)：

存在欧拉路径的充分必要条件：要么所有点出度均等于入度，要么除了两个点之外 其余点出度均等于入度 剩余两个点(起点)：出度比入度多一
另一个终点入度比出度多1

存在欧拉回路：所有点出度均等于入度

dfs求欧拉回路时 dfs到u节点 先将u节点拓展完 再把u节点相关的点全部搜完 再把u节点放到栈中 由于是回溯得到的结果 所以要倒序输出
用边判重 因为有很多重边 如果用点判重 每个点只会遍历一次

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 10, M = 4e5 + 10;
int ne[M], h[N], e[M], idx;
int type, ans[N], st[M], cnt, in[N], out[N], n, m, vis[M];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int x)
{
    for (int& i = h[x]; ~i;)
    {
        if (vis[i])
        {
            i = ne[i];//i是表头的一个别名 在指向下一条边的同时 顺便把表头更新
            continue;
        }
        vis[i] = 1;
        if (type == 1) vis[i ^ 1] = 1;
        int t;
        if (type == 1)
        {
            t = i / 2 + 1;
            if (i & 1) t = -t;
        }
        else t = i + 1;
        int j = e[i];
        i = ne[i];
        dfs(j);
        ans[++cnt] = t;
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> type >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        in[v]++;
        out[u]++;
        if (type == 1) add(v, u);//反向边
    }
    if (type == 1)
    {
        for (int i = 1; i <= n; i++)
        {
            if (in[i] + out[i] & 1)
            {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            if (in[i] != out[i])
            {
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (h[i] != -1)
        {
            dfs(i);
            break;
        }
    }
    //cout << cnt << " " << m << endl;
//  if(m==200000) cout<<cnt<<endl;
    if (cnt < m)
    {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    for (int i = cnt; i >= 1; i--)
    {
        cout << ans[i];
        if (i > 1) cout << " ";
    }

}