花椰菜君给了蒜头君 n 个单词,若是一个单词的最后一个字母和另外一个单词的第一个字母相同,那么两个单词就能够链接在一块儿组成一个新的单词。如今花椰菜君想要蒜头君计算一下,给定的 n 个单词是否能够所有链接在一块儿。
输入格式
第一行输入一个整数 nn,表明一共有 n 个单词(1≤n≤100,000)。
接下来输入 n 行,每行输入一个单词。单词均由小写字母组成,每一个单词长度不超过 20。
输出格式
输出一行,若是全部的单词均可以链接在一块儿而且能够造成一个环,那么输出Euler loop;若是全部单词均可以链接在一块儿,可是不会造成环,输出Euler path;若是全部单词不能连在一块儿,那么输出impossible。
样例输入
3
euler
ruby
jisuanke
样例输出
Euler pathios
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int have_put[50];
int rudu[50];
int chudu[50];
int dad[100050];
int getdad(int i)
{
if(dad[i]==i)return i;
return dad[i]=getdad(dad[i]);
}
void init()
{
for(int i=1;i<=n;i++)dad[i]=i;
memset(have_put,0,sizeof(have_put));
memset(rudu,0,sizeof(rudu));
memset(chudu,0,sizeof(chudu));
}
int main()
{
int u,v;
cin>>n;
init();
for(int i=1;i<=n;i++)
{
string a;
cin>>a;
u=a[0]-'a'+1;
v=a[a.size()-1]-'a'+1;
have_put[u]=1;
have_put[v]=1;
if(getdad(v)!=getdad(u))dad[getdad(u)]=getdad(v);
rudu[v]++;
chudu[u]++;
}
int c=getdad(u);
for(int i=1;i<=26;i++)
{
if(have_put[i]==0)continue;
if(getdad(i)!=c){
cout<<"impossible";
return 0;
}
}
int cnt1=0;
int cnt2=0;
if(n==1)
{
cout<<"Euler path";
return 0;
}
for(int i=1;i<=26;i++)
{
if(chudu[i]==rudu[i]+1)cnt1++;
else if(chudu[i]+1==rudu[i])cnt2++;
else if(rudu[i]!=chudu[i]){
cout<<"impossible";
return 0;
}
}
if(cnt1==1&&cnt2==1)cout<<"Euler path";
else if(cnt1==0&&cnt2==0)cout<<"Euler loop";
else cout<<"impossible";
return 0;
}