【模板】RMQ的LCA

#include
using namespace std;
const int z = 1024;
struct EDGE{
	int t, next;
	int w;
} edge[z*5];
int cnt, head[z];
void adedge(int f,int t,int w) {
	edge[++cnt].t = t;
	edge[cnt].w = w;
	edge[cnt].next = head[f];
	head[f] = cnt;
	return;
}
int tot, ver[z*2], depth[z*2], first[z], dis[z], dp[z][z];
bool visit[z];
void dfs(int u,int deep) {
	visit[u] = true;
	ver[++tot] = u;
	first[u] = tot;
	depth[tot] = deep;
	for(int i = head[u];i;i = edge[i].next) 
		if(!visit[edge[i].t]) {
			dis[edge[i].t] = dis[u]+edge[i].w;
			dfs(edge[i].t,deep+1);
			ver[++tot] = u;
			depth[tot] = deep;
		}
	return;
}
void ST(int n) {
	for(int i = 1;i <= tot;++i)
		dp[i][0] = i;
	for(int j = 1;(1< y) swap(x,y);
	int res = RMinQ_query(x,y);
	return ver[res];
}
int main() {
	int n, m;
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= m;++i) {
		int f, t;
		scanf("%d %d",&f,&t);
		adedge(f,t,1);
	}
	dfs(1,1);
	for(int i = 1;ver[i];++i) printf("%d ",ver[i]);
	return 0;
}