Doctor Pong has two arrays of integers : a1 , a2 , ......, aN and b1 , b2 , ......, bM . His student Rong wants to know what these numbers are, but Pong won’t tell him the numbers directly. So, Rong asks Pong a series of questions of the form "How big is ai+ bj ?", but his answers either "It’s at least c" or "It’s at most c". After getting Pong’s
responses, Rong tries to guess the numbers, but he cannot ?gure them out no matter how hard he tries. He starts to wonder if Pong has lied while answering some of the questions. Write a program to help Rong.
There are multiple test cases.
The ?rst line of input contains an integer T(1 ≤ T ≤ 100), indicating the number of test cases.
Each test case begins with a line containing three positive integers N, M, and Q, which denote the lengths of the Pong’s arrays and the number of questions that Rong asked. These numbers satisfy 2 ≤ N + M ≤ 2, 000 and 1 ≤ Q ≤ 10, 000.
Each of the next Q lines is of the form "i j <= c" or "i j >= c". The former represents ai + bj ≤ c, and the latter represents ai + bj ≥ c. It is guaranteed that c ≤ 100000.
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define inf 1e9+7
using namespace std;
const int N = 2e3+50;
int n,m,k;
char str[5];
int dis[N],inq[N],cnt[N],q[N*N];
vector<pair<int,int> >edg[N];
void init(){
for(int i=0;i<N;i++){
dis[i]=inq[i]=0;
edg[i].clear();
}
}
bool spfa(){
int r=0;
for(int i=1;i<=n+m;i++){
q[++r]=i;inq[i]=true;
cnt[i]=1;
}
while(r){
int u=q[r--];
inq[u]=false;
for(int i=0;i<edg[u].size();i++){
int v=edg[u][i].first;
int w=edg[u][i].second;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
if(!inq[v]){
q[++r]=v;
inq[v]=true;
cnt[v]++;
if(cnt[v]>n+m)return false;
}
}
}
}
return true;
}
int main()
{
int x,y,w,T;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++){
scanf("%d%d%s%d",&x,&y,str,&w);
if(str[0]==‘<‘){
edg[y+n].pb(mp(x,w));
}
else {
edg[x].pb(mp(y+n,-w));
}
}
if(spfa())puts("Honest Pong!");
else puts("Pong has lied!");
}
return 0;
}
