这是代码qwq

#include <bits/stdc++.h>

using namespace std;

int n , m;
vector <int> g[100010];
bool vis[100010];
queue <int> q;
bool a[100010];
void dfs(int u)
{
	cout << u << " ";
	vis[u] = true;
	for (int i = 0; i < g[u].size(); i++)
	{
		if (a[g[u][i]]== true)
		{
			if (vis[g[u][i]] == false)
			{
				dfs(g[u][i]);
			}
		}
		 
	}
}

void bfs(int u)
{
	if (q.empty())
	{
		return ;
	}
	for (int i = 0; i < g[u].size(); i++)
	{
		if (a[g[u][i]] == true)
		{
			if (vis[g[u][i]] == false)
			{
				q.push(g[u][i]);
				vis[g[u][i]] = true;
			}
			
		}
	}
	cout << q.front() << " ";
	int awa = q.front();
	q.pop();
	bfs(awa);
	
	
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x , y;
		cin  >> x >> y;
		a[x] = true;
		a[y] = true;
		g[x].push_back(y);
		
	
	}
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == true)
		{
			sort(g[i].begin(),g[i].end());
		}
	
	}
	
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == true)
		{
			if (vis[i] == false)
			{
				dfs(i);
			}
		}
		
		
	}
	cout << endl; 
	memset(vis , 0 , sizeof(vis));
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == true)
		{
			q.push(i);
			bfs(i);
			break;
		}
	}
	
	

	return 0;
}