#define NOFOOTER
#include "testlib.h"
#include <iostream>
#include <vector>
#include <map>

#pragma comment(linker,"/STACK:20000000")

using namespace std;

const int MAXV = 100000;

map<pair<int,int>, int> edges;
vector<int> mate[MAXV+1];
int nCnt, was[MAXV+1];

void dfs(int u){
	was[u]=1;
	++nCnt;
	for (int i=0; i<(int)mate[u].size(); ++i) if (!was[mate[u][i]]) dfs(mate[u][i]);
}

int main(int argc, char * argv[]){
	registerTestlibCmd(argc, argv);
	
	int n, m;
	n = inf.readInt();
	m = inf.readInt();
	
	for (int i=0; i<m; ++i) {
		int a, b;
		a = inf.readInt();
		b = inf.readInt();
		edges[make_pair(min(a,b),max(a,b))]++;
	}
	
	vector<int> cycle;
	int cnt=0;
	while (!ouf.seekEof() && ++cnt<=m+1){
		int u = ouf.readInt();
		cycle.push_back(u);
	}
	
	if (cnt > m+1) quitf(_wa,"Too many vertices (>= %d) in the cycle. n= %d, m = %d",cnt,n,m);
	
	int len = cycle.size();
	if (len < 2) quit(_wa,"Cycle is too short");
	if (cycle[0] != cycle[len-1]) quit(_wa,"First and last vertices don't match");
	
	for (int i=0; i<len-1; ++i) {
		int a = cycle[i], b=cycle[i+1];
		if (a>b) swap(a,b);
		if (--edges[make_pair(a,b)] < 0) quitf(_wa,"Edge between %d and %d was taken too many times",a,b);
	}
	
	for (map<pair<int,int>,int>::iterator it=edges.begin(); it!=edges.end(); ++it) if (it->second) {
		int a=it->first.first, b=it->first.second;
		mate[a].push_back(b);
		mate[b].push_back(a);
	}
	
	
	dfs(1);
	
	if (nCnt != n) quit(_wa,"The graph is not connected, after cycle removal");
	
	quitf(_ok,"n = %d, m = %d, cycle length = %d",n,m,len);
	return 0;	
}
