#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
vector<int> G[MAX];
int du[MAX];
int m, id;
map<string, int> hmap;
int TopSort() {
int tot = 0;
priority_queue<int> que;
for(int i=0; i<=id; i++)
if(du[i]==0) que.push(i);//将引用次数为0的id从小到大插入队列中
//当队列为空时说明所有id所对应的元素都被引用,则一定发生了错误;当队列不为空时则进入下列循环
while(!que.empty()) {
int x = que.top();
que.pop();
tot++;
for(int i=0; i<G[x].size(); i++) {
int u = G[x][i];
du[u]--;
if(!du[u])
que.push(u);
}
}
if(tot == id+1) return true;//进行出入队列元素的个数等于id的个数时说明没有发生错误
return false;
}
void doo() {
id = -1;
memset(du, 0, sizeof(du));//将数组du清空
hmap.clear();//将hmap清空
cin >> m;
for(int i=0; i<=m; i++)
G[i].clear();//将G的前i个元素清空
for(int i=0; i<m; i++) {
string a, b;
cin >> a >> b;
if(hmap.count(a) == 0)
hmap.insert(pair<string, int>(a, ++id));// 当输入的a在当前的hmap中不存在时,就赋予a一个id
if(hmap.count(b) == 0)
hmap.insert(pair<string, int>(b, ++id));// 当输入的b在当前的hmap中不存在时,就赋予b一个id
G[hmap[b]].push_back(hmap[a]);//将a的id加入b所对应的数组中
du[hmap[a]]++;//将a所对应的引用b的次数加1
}
cout << (TopSort() ? "Passed" : "Failed" ) << endl;
}
int main()
{
int T;
cin >> T;
while(T--)
doo();
return 0;
}
/**
2
8
client.cpp client.h
client.h server.h
server.cpp server.h
server.h common.h
client.h common.h
common.cpp common.h
common.h gtest.h
common.h glog.h
4
work.cpp client.cpp
client.cpp server.cpp
server.cpp adhoc.cpp
adhoc.cpp work.cpp
*/