# Poj Solution 2513

```http://poj.org/problem?id=2513

//* @author:
import java.io.IOException;

public class Main {
int sum = 0;
int time[] = new int[500000];
int parent[] = new int[500000];
int rank[] = new int[500000];
trieT root;

void ini() {
root = new trieT();
for (int i = 0; i < 500000; i++)
parent[i] = i;
}

public static void main(String[] args) throws IOException {
Main p = new Main();
p.ini();
int a = 0;
int b = 0;
int qtime = 0;

String tmp = re.readLine();
while (tmp!=null) {

a = p.insert(tmp.split(" ")[0].toCharArray(), p.root);
b = p.insert(tmp.split(" ")[1].toCharArray(), p.root);
p.time[a]++;
p.time[b]++;
if (a != b)
p.union(a, b);
}

for (int i = 0; i < p.sum; i++)
if (p.time[i] % 2 != 0)
qtime++;
int k = p.find(0);
for (int i = 1; i < p.sum; i++)
if (k != p.find(i)) {
System.out.println("Impossible");
return;
}
if (qtime <= 2)
System.out.println("Possible");
else
System.out.println("Impossible");

}

int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}

void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa == fb)
return;
if (rank[fa] > rank[fb])
parent[fb] = fa;
else if (rank[fa] < rank[fb])
parent[fa] = fb;
else {
parent[fa] = fb;
rank[fb]++;
}
}

int insert(char[] key, trieT trie) {
for (int i = 0; i < key.length; i++) {
int index = key[i] - 'a';
if (trie.child[index] == null) {
trie.child[index] = new trieT();
}
trie = trie.child[index];
}
if (trie.count == -1)
trie.count = sum++;
return trie.count;
}
}
class trieT {
int count = -1;
trieT child[] = new trieT[26];

public trieT() {
for (int i = 0; i < 26; i++)
child[i] = null;

}

}
```
This entry was posted in poj. Bookmark the permalink.