提交记录

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#define hh putchar('\n')
#define kg putchar(' ')
#define debug puts("debug")
//#define int long long
//#define int __int128
namespace quickread{
	template<typename T> void read(T &x){
		x=0;char c=getchar();T neg=0;
		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
		if(neg) x=(~x)+1;
	}
	template<typename T> void write(T x){
		if(x<0) putchar('-'),x=~x+1;
		if(x>9) write(x/10);
		putchar(x%10^48);
	}
	inline string readstr(){
    	char ch=getchar();string str="";
		while(!isalnum(ch)) ch=getchar();
		while(isalnum(ch)){str+=ch;ch=getchar();}
		return str;
	}
	inline char readchar(){
		char ch=getchar();
		while(!isalnum(ch)) ch=getchar();
		return ch;
	}
}
using namespace quickread;
const int N=1e6+10,inf=2147483647;
int n,m,bg,ed;
bool vis[N];
stack<int> st;
unordered_map<string,int> _index;
int id(string x){if(!_index[x]) _index[x]=++n;return _index[x];}
vector<int> g[N];
vector<int>::iterator it[N];
bool hierholzers(){
	for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end()),it[i]=g[i].begin();
	for(int i=1;i<=n;i++) if(g[i].size()&1){
		if(!bg) bg=i;
		else if(!ed) ed=i;
		else return 0;
	}
	if(!bg){
		bg=n+1;
		for(int i=1;i<=n;i++) if(g[i].size()&&bg>i) bg=i;
	}
	return 1;
}
void dfs(int u){
	while(it[u]!=g[u].end()){
		int v=*it[u];it[u]++;
		if(vis[u]) continue;
		vis[u]=1;
		dfs(v);
	}
	st.push(u);
}
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	string s1,s2;
	while(cin>>s1>>s2){
		++m;
		int u=id(s1),v=id(s2);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if(hierholzers()){
		dfs(bg);
		if(st.size()==m+1) puts("Possible");
		else puts("Impossible");
	}else puts("Impossible");
	return 0;
}