#include<iostream>
#include<fstream>
using namespace std;
int a[101][101],l[101],n,m,k;
ifstream f("24.in");
void citire()
{
    f>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x][y]=1;
        a[y][x]=1;
    }
    f>>k;
    for(int i=1;i<=k;i++)
        f>>l[i];
}
int verif_l_hamiltonian()
{
    if(k!=n+1)return 0;
    if(l[1]!=l[k])return 0;
    for(int i=1;i<=k-2;i++)
        for(int j=i+1;j<=k-1;j++)
        if(l[i]==l[j])return 0;

    for(int i=1;i<k;i++)
        if(a[l[i]][l[i+1]]!=1)return 0;
    return 1;
}
int verif_l_eulerian()
{
    int i,j;
    if(k!=m+1)return 0;
    if(l[1]!=l[k])return 0;
    for(i=1;i<=k-1;i++)
        if(a[l[i]][l[i+1]]==0) return 0;
    for(i=1;i<=k-2;i++)
        for(j=i+1;j<k-1;j++)
        if((l[i]==l[j]&&l[i+1]==l[j+1])||(l[i]==l[j+1]&&l[i+1]==l[j]))
        return 0;
    return 1;
}
int main()
{
    citire();
    if(verif_l_hamiltonian()==1)cout<<"Sirul poate reprezenta un ciclu hamiltonian"<<endl;
    else cout<<"Sirul nu poate reprezenta un ciclu hamiltonian"<<endl;
    if(verif_l_eulerian()==1)cout<<"Sirul poate reprezenta un ciclu eulerian"<<endl;
    else cout<<"Sirul nu poate reprezenta un ciclu eulerian"<<endl;

}