8660: Winner Prediction

A tournament consisting of n participants is currently taking place. The players are numbered from 1 to n. Every match is between two participants, and there are no draws. The participant who wins the most matches wins the entire tournament; if there are multiple participants tied at the first place, all of them win the tournament.

At the current state, some matches have ended, and others are yet to start. You are given the results of all ended matches. Write a program to determine whether it is possible for player 1 to win the tournament.

You are given T independent test cases. Solve each of them.

The first line of input consists of a single integer $T(1\le T\le 100)$, indicating the number of test cases. Then $T$ test cases follow.

Each of the T test cases consists of multiple lines.

The first line contains three integers n,m1,m2(1≤n≤500,1≤m1,m2≤1000), indicating the number of participants, the number of ended matches and the number of upcoming matches.

Each of the next m1 lines contains three space-separated integers $x,y,z(1\le x,y\le n,x！=y,0\le z\le 1)$, indicating an ended match between player $x$ and player y , z = 1 means player $x$ won the match and z=0 means player y won the match.

Each of the next m_2m2 lines contains two space-separated integers $x,y(1\le x,y\le n,x！=y)$, indicating an upcoming match between player $x$ and player $y$.